这个板子的细节不少，大概思路就是每次用SPFA找增广路来增广。用SPFA之后可以找的就不仅仅是最短路，所以也会有其他奇奇怪怪的费用问题。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define inf 1000000000 5 using namespace std; 6 int vert,edg,S,T,ansf,ansc,que[100005],dist[100005],pre[5005]; 7 int tot,fr[5005],frr[100005],to[100005],nxt[100005],f[100005],w[100005]; 8 bool inq[100005]; 9 void adde(int p,int q,int F,int W) 10 {to[tot]=q;frr[tot]=p;f[tot]=F; w[tot]=W;nxt[tot]=fr[p];fr[p]=tot++;} 11 bool spfa(); 12 int main() 13 { 14 memset(fr,-1,sizeof(fr)); 15 scanf("%d%d%d%d",&vert,&edg,&S,&T); 16 int i,p,q,F,W; 17 for(i=1;i<=edg;i++) 18 { 19 scanf("%d%d%d%d",&p,&q,&F,&W); 20 adde(p,q,F,W); adde(q,p,0,-W); 21 } 22 int minn,now; 23 while(spfa()) 24 { 25 minn = inf; 26 for(now=T;now!=S;now=frr[pre[now]]) minn = min(minn,f[pre[now]]); 27 ansf += minn; 28 for(now=T;now!=S;now=frr[pre[now]]) 29 { 30 f[pre[now]]-=minn; f[pre[now]^1] += minn; 31 ansc += minn*w[pre[now]]; 32 } 33 } 34 printf("%d %d",ansf,ansc); 35 return 0; 36 } 37 bool spfa() 38 { 39 int i,l=0,r=0,now,t; 40 for(i=1;i<=vert;i++) dist[i] = inf; 41 memset(inq,false,sizeof(inq)); 42 dist[S] = 0; que[++r] = S; inq[S] = true; 43 while(l<r) 44 { 45 now = que[++l]; inq[now] = false; 46 for(i=fr[now];i!=-1;i=nxt[i]) 47 { 48 t = to[i]; 49 if(f[i]&&dist[t]>dist[now]+w[i]) 50 { 51 dist[t] = dist[now]+w[i]; 52 pre[t] = i; 53 if(!inq[t]) 54 { 55 que[++r] = t; 56 inq[t] = true; 57 } 58 } 59 } 60 } 61 if(dist[T]==inf) return false; 62 return true; 63 }