题解 P3381 【【模板】最小费用最大流】

· · 题解

思路：费用流

因为要注意费用的问题，所以用SPFA找费用最小的增广路，不要用Dijkstra（因为有负边权）（然而一般情况下SPFA更好写，所以这个警告是废话）；

然后增广ap()。

几个注意的地方：

反边费用为其对应边的相反数；

队列首尾指针记得清零；（RE了50%左右）

有一种常（la）数（ji）级优化技巧叫先留个坑，反边随用随建。（优化程度达不到O（）*0.5，但是够用，而且很好实现）；

一个两个点一直被卡，又看不懂楼下大神题解（像我一样）的同学可以尝试一下。

代码实现：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define maxn 5010
 4 #define maxm 100010
 5 #define maxt 2139062143
 6 int n,m,s,t,nflow,nfee,flow,fee;
 7 int a,b,c,d;
 8 long long la,lb;
 9 int h[maxn],hs=1;
10 struct edge{int s,n,w,f;}e[maxm];
11 int w[maxn];
12 int p[maxn][2];
13 int q[maxm],head,tail;
14 int min(int x,int y){return x<y?x:y;}
15 int spfa(){
16     memset(w,0x7f,sizeof(w));
17     head=tail=0;
18     q[head++]=s,w[s]=0;
19     while(head>tail){
20         a=q[tail++];
21         for(int i=h[a];i;i=e[i].n)
22         if(e[i].w){
23             la=e[i].f,lb=w[a],la+=lb,lb=w[e[i].s];
24             if(la<lb){
25                 w[e[i].s]=la;
26                 p[e[i].s][0]=i;
27                 p[e[i].s][1]=a;
28                 q[head++]=e[i].s;
29             }
30         }
31     }
32     return w[t];
33 }
34 int ap(int k,int v){
35     if(k==s) return v;
36     int ret=ap(p[k][1],min(e[p[k][0]].w,v));
37     if(!e[p[k][0]^1].f) e[p[k][0]^1]=(edge){p[k][1],h[k],0,-e[p[k][0]].f},h[k]=p[k][0]^1;
38     e[p[k][0]].w-=ret;
39     e[p[k][0]^1].w+=ret;
40     return ret;
41 }
42 bool Mcmf(){
43     nfee=spfa();
44     if(nfee==maxt) return false;
45     nflow=ap(t,maxt);
46     flow+=nflow;
47     fee+=nflow*nfee;
48     return true;
49 }
50 int main(){
51     scanf("%d%d%d%d",&n,&m,&s,&t);
52     for(int i=1;i<=m;i++){
53         scanf("%d%d%d%d",&a,&b,&c,&d);
54         e[++hs]=(edge){b,h[a],c,d},h[a]=hs++;
55     }
56     while(Mcmf());
57     printf("%d %d\n",flow,fee);
58     return 0;
59 }
来源：http://www.cnblogs.com/J-william/p/6506067.html