hdu-4322-Candy-费用流

发布时间:2014-10-22 18:58:27编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu-4322-Candy-费用流",主要涉及到hdu-4322-Candy-费用流方面的内容,对于hdu-4322-Candy-费用流感兴趣的同学可以参考一下。

http://blog.csdn.net/julyana_lin/article/details/8095405 #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<algorithm> using namespace std; const int N = 1010;//点 const int M = 2 * 10010;//边 const int inf = 1000000000; struct Node{//边,点f到点t,流量为c,费用为w int f, t, c, w; }e[M]; int next1[M], point[N], dis[N], q[N], pre[N], ne;//ne为已添加的边数,next,point为邻接表,dis为花费,pre为父亲节点 bool u[N]; void init(){ memset(point, -1, sizeof(point)); ne = 0; } void add_edge(int f, int t, int d1, int d2, int w){//f到t的一条边,流量为d1,反向流量d2,花费w,反向边花费-w(可以反悔) e[ne].f = f, e[ne].t = t, e[ne].c = d1, e[ne].w = w; next1[ne] = point[f], point[f] = ne++; e[ne].f = t, e[ne].t = f, e[ne].c = d2, e[ne].w = -w; next1[ne] = point[t], point[t] = ne++; } bool spfa(int s, int t, int n){ int i, tmp, l, r; memset(pre, -1, sizeof(pre)); for(i = 0; i < n; ++i) dis[i] = inf; dis[s] = 0; q[0] = s; l = 0, r = 1; u[s] = true; while(l != r) { tmp = q[l]; l = (l + 1) % (n + 1); u[tmp] = false; for(i = point[tmp]; i != -1; i = next1[i]) { if(e[i].c && dis[e[i].t] > dis[tmp] + e[i].w) { dis[e[i].t] = dis[tmp] + e[i].w; pre[e[i].t] = i; if(!u[e[i].t]) { u[e[i].t] = true; q[r] = e[i].t; r = (r + 1) % (n + 1); } } } } if(pre[t] == -1) return false; return true; } void MCMF(int s, int t, int n, int &flow, int &cost){//起点s,终点t,点数n,最大流flow,最小花费cost int tmp, arg; flow = cost = 0; while(spfa(s, t, n)) { arg = inf, tmp = t; while(tmp != s) { arg = min(arg, e[pre[tmp]].c); tmp = e[pre[tmp]].f; } tmp = t; while(tmp != s) { e[pre[tmp]].c -= arg; e[pre[tmp] ^ 1].c += arg; tmp = e[pre[tmp]].f; } flow += arg; cost += arg * dis[t]; } } //建图前运行init() //节点下标从0开始 //加边时运行add_edge(a,b,c,0,d)表示加一条a到b的流量为c花费为d的边(注意花费为单位流量花费) //特别注意双向边,运行add_edge(a,b,c,0,d),add_edge(b,a,c,0,d)较好,不要只运行一次add_edge(a,b,c,c,d),费用会不对。 //求解时代入MCMF(s,t,n,v1,v2),表示起点为s,终点为t,点数为n的图中,最大流为v1,最大花费为v2 int map[15][15]; int b[15]; int main() { int t; cin>>t; int ans=0; while(t--) { ans++; int n,m,k,i,j,sum=0; cin>>n>>m>>k; for(i=1;i<=m;i++) { cin>>b[i]; sum+=b[i]; } for(i=1;i<=m;i++) for(j=1;j<=n;j++) cin>>map[i][j]; init(); for(i=1;i<=n;i++) add_edge(0,i,1,0,0); for(i=1;i<=m;i++){ for(j=1;j<=n;j++) { if(map[i][j]==1) { add_edge(j,i+n,1,0,0); } } add_edge(i+n,n+m+1,b[i]/k,0,-k); if(b[i]%k>1) add_edge(i+n,n+m+1,1,0,-(b[i]%k)); } int flow,cost; MCMF(0,n+m+1,n+m+2,flow,cost); if(n-flow>=sum+cost) cout<<"Case #"<<ans<<": "<<"YES"<<endl; else cout<<"Case #"<<ans<<": "<<"NO"<<endl; } }


上一篇:android下载器, 运行错误...
下一篇:Ningbo [1220] SPY(题目有点难懂,读懂题目题很简单)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款