最小费用最大流 模板

#include <stdio.h> #include <iostream> using namespace std; struct edge{ int u,v,c,f,next; edge(){ u=v=c=f=0; next=-1; } edge(int x,int y,int z,int w,int t){ u=x;v=y;c=z;f=w;next=t; } } e[Maxm]; void add(int u,int v,int c,int f){ len++; e[len]=edge(u,v,c,f,head[u]); head[u]=len; } int spfa(){ queue <int> q; for(i=1;i<=n;i++)    vis[i]=0; q.push(s); while(!q.empty()){ x=q.front(); q.pop(); vis[x]=0; for(i=head[x];i!=-1;i=e[i].next){ if(e[i].c>e[i].f&&e[i].w+dis[u]>dis[v]){    dis[e[i].v]=dis[e[i].u]+e[i].w;    pre[e[i].v]=i;    a[e[i].v]=min(a[e[i].u],e[i].c-e[i].f);    if(!vis[e[i].v]){        q.push(e[i].v);        vis[e[i].v]=1;    } } } } if(dis[t]==inf)    return 0; flow+=a[t]; cost+=dis[t]*a[t]; x=t; while(x!=s){ e[pre[x]].f+=a[t]; e[pre[x]^1].f-=a[t]; x=e[pre[x]].u; } return 1; } int main(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); for return 0; }