设为首页 加入收藏

TOP

POJ 1815 Friendship(最小割)(二)
2015-07-20 17:59:31 来源: 作者: 【 】 浏览:3
Tags:POJ 1815 Friendship 最小
INE_JUDGE freopen("/home/fcbruce/文档/code/t","r",stdin); #endif // ONLINE_JUDGE int n,_u,_v,_w,s,t; scanf("%d%d%d",&n,&_u,&_v); s=_u+n;t=_v; e_max=0; memset(fir,-1,sizeof fir); for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { scanf("%d",&_w); if (!_w) continue; if (i==_u && j==_v || i==_v && j==_u) { printf("NO ANSWER!\n"); return 0; } add_edge(i+n,j,INF); } } for (int i=1;i<=n;i++) { that_edge[i]=e_max; add_edge(i,i+n,1); } int temp=max_flow(s,t); bool first=false; printf("%d\n",temp); for (int i=1;i<=n && temp;i++) { if (i==s-n || i==t) continue; if (!flow[that_edge[i]]) continue;//最小割边一定满流,考虑逆否命题,不满流的边一定不是最小割边 cap[that_edge[i]]=0; int k=max_flow(s,t); if (k

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇POJ 1577 Falling Leaves 下一篇codeforces 453A Little Pony and..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: