USACO Section 5.4 Telecowmunication - 构图网络流,最小割

网友投稿 264 2022-09-14

USACO Section 5.4 Telecowmunication - 构图网络流,最小割

我开始是用DFS不断的搜路径..搜出一条路径后记录下~~枚举删的一个点使这条路径作废..然后继续DFS搜路径~~直道搜不到路径~~就找到了一组解~~我这样写还过了3个点~~但到第4个点就是无限超时~~跑这组数据我是等了5分钟出不来~~好吧~~显然我这个土方法是行不通的..

思考了很久还是没有结果...还是去网上找了...才恍然大悟..原来这道题是个网络流...对最小割的我一直是很不熟悉...通过这题就算是学习到了一种把点变成线的思维..同时又加深了对最小割的理解...说白了..最小割就是去掉之和最小的边..使得一个连同的有向图变成一个包括起点在内的点集和一个包括终点在内的点集...

Nowcow关于此题的题解:  ​​ ID: zzyzzy12 LANG: C++ TASK: telecow*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; int M,N,C1,C2,arc[205][205];int MinFlow,ans[205],t[205],way[205]; queue myqueue;bool BFS(){ int h,i; memset(t,0,sizeof(t)); t[C1]=1; myqueue.push(C1); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); for (i=1;i<=N;i++) if (arc[h][i] && !t[i]) { t[i]=t[h]+1; myqueue.push(i); } } return t[C2];}bool DFS(int p,int MIN){ int i; way[++M]=p; if (p==C2) { MinFlow+=MIN; for (i=1;i

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

标签：数据
上一篇:CodeForces Round #118 (185A) - Plant
下一篇:DoMarketing-营销智库：欧莱雅左手“M姐”右手“欧爷”，品牌为何钟爱虚拟偶像？
相关文章

 发表评论

暂时没有评论，来抢沙发吧~