最小费用最大流spfa做法
1.以费用为边权，求源到汇的最短路径
2.从最短路径上找到剩余流量最小的边
3.把整条路径上的边的流量都减少那么多，并更新费用
4.重复做1-3，直到找不到从源到汇的路径。
Slf优化：每次入队时候把这个点的费用与队首的点的费用相比较，如果比那个点的费用小，插到队头，否则插到队尾。
这个优化对于普通的最短路问题同样有优化，对于没有负权边的图优化尤其大。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; struct data{ int to,cap,cost,next; }g[80001]; int h[2101],d[2101],k=1,used[201],que[100000],head,tail,last[2101],ans=0; int INF; inline int read(){ int x; bool f; char c; for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-'); for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0'); return f?-x:x; } void add(int from,int to,int cap,int cost) { g[++k].next=h[from];h[from]=k;g[k].to=to;g[k].cap=cap;g[k].cost=cost; g[++k].next=h[to];h[to]=k;g[k].to=from;g[k].cap=0;g[k].cost=-cost; } bool spfa(int s,int t) { memset(last,0,sizeof(last)); memset(d,127/3,sizeof(d));INF=d[0]; memset(used,0,sizeof(used)); head=tail=50000;que[tail++]=s;used[s]=1;d[s]=0; while(head<=tail) { int u=que[head++]; for(int i=h[u];i;i=g[i].next) { if(g[i].cap&&d[u]+g[i].cost<d[g[i].to]) { d[g[i].to]=d[u]+g[i].cost;last[g[i].to]=i; if(!used[g[i].to]) { if(d[g[i].to]<d[que[head]])que[--head]=g[i].to; else que[tail++]=g[i].to;used[g[i].to]=1; } } } used[u]=0; } if(d[t]==INF)return false; return true; } void mcf(int t) { int minn=INF; for(int i=last[t];i;i=last[g[i^1].to])minn=min(minn,g[i].cap); for(int i=last[t];i;i=last[g[i^1].to]) { ans+=g[i].cost*minn; g[i].cap-=minn;g[i^1].cap+=minn; } }
while(spfa(1,n))mcf(n);
费用流的原始对偶(Primal-Dual)算法
1我们每次都先从汇点走反边往回用spfa求一次最短路
2对于一条边<i,j>,如果其在最短路上，设j更靠近T，则一定满足d[i]-cost[i][j]==d[j],我们就可以判断<i,j>是否在最短路上，如果是，就沿着这条路增广
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int inq[100000],d[100000],h[100000],q[200000],from[100000],head,tail,k=1,INF=999999999,ans=0,used[100000]; struct data{ int to,cap,cost,next; }g[1000000]; void add(int from,int to,int cap,int cost) { g[++k].next=h[from];h[from]=k;g[k].to=to;g[k].cap=cap;g[k].cost=cost; g[++k].next=h[to];h[to]=k;g[k].to=from;g[k].cap=0;g[k].cost=-cost; } bool spfa(int s,int t) { head=tail=100000; memset(d,127/3,sizeof(d));INF=d[0]; memset(inq,0,sizeof(inq)); q[tail++]=t;d[t]=0;inq[t]=1; while(head<=tail) { int u=q[head++];inq[u]=0; for(int i=h[u];i;i=g[i].next) { if(g[i^1].cap&&d[u]+g[i^1].cost<d[g[i].to]) { d[g[i].to]=d[u]+g[i^1].cost; if(!inq[g[i].to]) { if(d[g[i].to]<d[q[head]])q[--head]=g[i].to; else q[tail++]=g[i].to;inq[g[i].to]=1; } } } } return d[s]!=INF; } int dfs(int u,int t,int f) { used[u]=1; if(u==t)return f; int _used=0,w; for(int i=h[u];i;i=g[i].next) { if(!used[g[i].to]&&g[i].cap&&d[u]-g[i].cost==d[g[i].to]) { w=dfs(g[i].to,t,min(g[i].cap,f-_used)); if(w) { _used+=w;g[i].cap-=w;g[i^1].cap+=w;ans+=w*g[i].cost; if(_used==f)return f; } } } return _used; } void PD(int s,int t) { while(spfa(s,t)) { used[t]=1; while(used[t]) { memset(used,0,sizeof(used)); dfs(s,t,INF); } } }