【模板】 最小费用最大流

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define MAXN 500010
 6 
 7 using namespace std;
 8 
 9 int n,m,s,t,ans1,ans2;
10 
11 int pre[MAXN],fee[MAXN];
12 
13 struct node {
14     int to;
15     int next;
16     int val;
17     int cost;
18 };
19 node e[MAXN];
20 
21 int head[MAXN],tot=1;
22 
23 bool vis[MAXN];
24 
25 const int INF=0x7fffffff;
26 
27 queue q;
28 
29 inline void read(int&x) {
30     int f=1;x=0;char c=getchar();
31     while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}
32     while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}
33     x=x*f;
34 }
35 
36 inline void add(int x,int y,int val,int cost) {
37     e[++tot].to=y;
38     e[tot].cost=cost;
39     e[tot].val=val;
40     e[tot].next=head[x];
41     head[x]=tot;
42 }
43 
44 inline void add_edge(int x,int y,int val,int cost) {
45     add(x,y,val,cost);
46     add(y,x,0,-cost);
47 }
48 
49 inline int max_flow() {
50     int flow=INF;
51     for(int i=pre[t];i;i=pre[e[i^1].to])
52       flow=min(flow,e[i].val);
53     for(int i=pre[t];i;i=pre[e[i^1].to]) 
54       e[i].val-=flow,e[i^1].val+=flow;
55     return flow;
56 }
57 
58 inline bool spfa() {
59     for(int i=1;i<=n;i++) vis[i]=false,pre[i]=-1,fee[i]=INF;
60     while(!q.empty()) q.pop();
61     fee[s]=0;
62     vis[s]=true;
63     pre[s]=0;
64     q.push(s);
65     while(!q.empty()) {
66         int u=q.front();
67         q.pop();
68         vis[u]=false;
69         for(int i=head[u];i!=-1;i=e[i].next) {
70             int to=e[i].to;
71             if(fee[u]+e[i].cost

代码