费用流即最小费用最大流
白书粉书真是神器23333333
先贴上粉书上的模板：
struct Edge { int from,to,cap,flow,cost; Edge(int u,int v,int c,int f,int w): from(u),to(v),cap(c),flow(f),cost(w) {} }; int n,m; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n) { //this->n=n; 粉书上原版有这一句，但明显会报错。感觉去掉也没什么影响... for (int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap,int cost) { edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s,int t,int &flow,long long &cost) //用队列优化过，感觉和SPFA一样了 { for (int i=0;i<n;i++) d[i]=INF; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; p[s]=0; a[s]=INF; queue<int> Q; Q.push(s); while (!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=0; for (int i=0;i<G[u].size;i++) { Edge& e=edges[G[u][i]]; if (e.cap>e.flow && d[e.to]>d[u]+e.cost()) { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if (!inq[e.to]) { Q.push(e.to); inq[e.to]=1; } } } } if (d[t]==INF) return false; flow+=a[t]; cost+=(long long)d[t] * (long long)a[t]; for (int u=t;u!=s;u=edges[p[u]].from) { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; } return true; } int MCMF(int s,int t,long long& cost) //s:起点；t:汇点； { int flow=0; cost=0; //flow:求出来的最大流 cost:求出来的费用 while (BellmanFord(s,t,flow,cost)); return flow; }
Exercise：POJ2516
#include <iostream> #include <cstring> #include <vector> #include <queue> using namespace std; #define INF 9999999 struct Edge { int from,to,cap,flow,cost; Edge(int u,int v,int c,int f,int w): from(u),to(v),cap(c),flow(f),cost(w) {} }; const int maxn=500; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; int flow,cost; int ne[60][60],me[60][60],ce[60][60][60]; int tm,tn,tk,x,m,n,ans,sum; void init(int n) { //this->n=n; for (int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap,int cost) { edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s,int t,int &flow,int &cost) { for (int i=0;i<n;i++) d[i]=INF; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; p[s]=0; a[s]=INF; queue<int> Q; Q.push(s); while (!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=0; for (int i=0;i<G[u].size();i++) { Edge& e=edges[G[u][i]]; if ((e.cap>e.flow)&&(d[e.to]>d[u]+e.cost)) { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if (!inq[e.to]) { Q.push(e.to); inq[e.to]=1; } } } } if (d[t]==INF) return false; flow+=a[t]; cost+=d[t]*a[t]; for (int u=t;u!=s;u=edges[p[u]].from) { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; } return true; } /* int MCMF(int s,int t,long long& cost) { flow=0; cost=0; while (BellmanFord(s,t,flow,cost)); return flow; } */ int main() { while (cin>>tn>>tm>>tk) { if (tn==0&&tm==0&&tk==0) break; else { for (int i=1;i<=tn;i++) for (int j=1;j<=tk;j++) cin>>ne[i][j]; //[1..tn][1..k] //ne[i][k]：shopkeeper-i需要的货物-k的数量 for (int i=1;i<=tm;i++) for (int j=1;j<=tk;j++) cin>>me[i][j]; //[1..tm][1..k] //me[i][k]：supply-i供应的货物-k的数量 for (int x=1;x<=tk;x++) for (int i=1;i<=tn;i++) for (int j=1;j<=tm;j++) cin>>ce[x][i][j]; //[1..k][1..tn][1..tm] //ce[k][i][j]：对于货物-k，从supply-j运到shopkeeper-i的花费，对应图中m[j]点到n[i]点的每一条边 ans=0; for (int x=1;x<=tk;x++) { sum=0; n=tn+tm+2; init(n); for (int i=1;i<=tm;i++) for (int j=tm+1;j<=tm+tn;j++) AddEdge(i,j,me[i][x],ce[x][j-tm][i]); for (int i=1;i<=tm;i++) AddEdge(0,i,me[i][x],0); //AddEdge(0,i,INF,0); //连接超级起点的边：费用为0，流量为supply-i的供应量 for (int i=tm+1;i<=tm+tn;i++) AddEdge(i,n-1,ne[i-tm][x],0); //AddEdge(i,n-1,INF,0); //连接超级终点的边：费用为0，流量为shopkeeper-i的需求量 //Reference：http://blog.csdn.net/lyy289065406/article/details/6742534 //注意因为这里有限制：只要流量能满足shopkeeper需求即可，没必要追求最大。 //所以不能把这些边的流量设成INF(无穷大) flow=0; cost=0; while (BellmanFord(0,n-1,flow,cost)); for (int i=1;i<=tn;i++) sum+=ne[i][x]; if (flow<sum) ans=-1; if (ans!=-1) ans+=cost; } cout<<ans<<endl; } } return 0; }
Reference：
http://blog.csdn.net/swordholy/article/details/4558617
http://blog.csdn.net/lyy289065406/article/details/6742534
http://blog.csdn.net/ls_0222/article/details/6817077
还有个神器叫zkw费用流，刷完二分图再看：
http://www.artofproblemsolving.com/blog/54262