首页 > 代码库 > P2740 [USACO4.2]草地排水Drainage Ditches
P2740 [USACO4.2]草地排水Drainage Ditches
题目背景
在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。
题目描述
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
输入输出格式
输入格式：
第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫John已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。
第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。
输出格式：
输出一个整数，即排水的最大流量。
输入输出样例
输入样例#1：
5 41 2 401 4 202 4 202 3 303 4 10
输出样例#1：
50
说明
题目翻译来自NOCOW。
USACO Training Section 4.2
裸地最大流问题，Dinic算法
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #define lli long long int 8 using namespace std; 9 const int MAXN=300001; 10 const int maxn=0x7fffff; 11 void read(int &n) 12 { 13 char c=‘+‘;int x=0;bool flag=0; 14 while(c<‘0‘||c>‘9‘) 15 {c=getchar();if(c==‘-‘)flag=1;} 16 while(c>=‘0‘&&c<=‘9‘) 17 {x=x*10+c-48;c=getchar();} 18 flag==1?n=-x:n=x; 19 } 20 struct node 21 { 22 int u,v,flow,cap,nxt; 23 }edge[MAXN]; 24 int head[MAXN]; 25 int num=0; 26 int n,m,S,T; 27 int dis[MAXN]; 28 int vis[MAXN]; 29 int cur[MAXN]; 30 void add_edge(int x,int y,int z) 31 { 32 edge[num].u=x; 33 edge[num].v=y; 34 edge[num].cap=z; 35 edge[num].flow=0; 36 edge[num].nxt=head[x]; 37 head[x]=num++; 38 } 39 bool bfs(int bg,int ed) 40 { 41 memset(dis,-1,sizeof(dis)); 42 queue<int>q; 43 q.push(bg); 44 dis[bg]=0; 45 while(!q.empty()) 46 { 47 int p=q.front(); 48 q.pop(); 49 for(int i=head[p];i!=-1;i=edge[i].nxt) 50 { 51 if(dis[edge[i].v]==-1&&edge[i].cap>edge[i].flow) 52 { 53 vis[edge[i].v]=1; 54 dis[edge[i].v]=dis[edge[i].u]+1; 55 q.push(edge[i].v); 56 } 57 } 58 } 59 if(dis[ed]==-1) 60 return 0; 61 else return 1; 62 } 63 int dfs(int now,int a)// a:所有弧的最小残量 64 { 65 if(now==T||a<=0) 66 return a; 67 68 int flow=0,f; 69 for(int i=head[now];i!=-1;i=edge[i].nxt) 70 { 71 if(dis[now]+1==dis[edge[i].v]&&edge[i].cap-edge[i].flow>0) 72 { 73 f=dfs(edge[i].v,min(a,edge[i].cap-edge[i].flow)); 74 edge[i].flow+=f; 75 edge[i^1].flow-=f; 76 flow+=f; 77 a-=f; 78 if(a<=0)break; 79 } 80 } 81 return flow; 82 } 83 void Dinic(int S,int T) 84 { 85 int ansflow=0; 86 for(int i=1;i<=n;i++) 87 cur[i]=head[i]; 88 while(bfs(S,T))// 求出层级 89 ansflow+=dfs(S,maxn); 90 printf("%d",ansflow); 91 92 } 93 int main() 94 { 95 read(m);read(n); 96 // swap(n,m); 97 S=1;T=n; 98 // read(S);read(T); 99 for(int i=1;i<=n;i++)100 head[i]=-1;101 for(int i=1;i<=m;i++)102 {103 int x,y,z;104 read(x);read(y);read(z);105 add_edge(x,y,z);106 add_edge(y,x,0);107 }108 Dinic(S,T);109 return 0;110 }
P2740 [USACO4.2]草地排水Drainage Ditches
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。