[最小费用最大流]UVa1658

[最小费用最大流]UVa1658

这种问题难点仅在于建模

理解透彻原模型！

#includeusing namespace std;const int maxn = 10000 + 100;const int INF = 0x7f7f7f7f;typedef long long LL;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) {}};struct MCMF{ int n,m; vector edges; vector 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 Q; Q.push(s); while(!Q.empty()){ int u=Q.front(); Q.pop(); inq[u]=0; for(int i=0;ie.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+=(LL) d[t]*(LL)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 MincostMaxdflow(int s,int t,int limit,LL & cost){ int flow=0; cost=0; while(flow

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。