首页 > 代码库 > [USACO4.2]Drainage Ditches
[USACO4.2]Drainage Ditches
练习网络流的好题目,这里给出的是Dinic
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=250; 4 int n,m; 5 struct Dinic{ 6 int G[N][N],dis[N]; 7 void build(){ 8 memset(G,0,sizeof G); 9 for(int i=1;i<=m;++i){ 10 int u,v,f; 11 scanf("%d%d%d",&u,&v,&f); 12 G[u][v]+=f; 13 } 14 } 15 bool BFS(){ 16 queue<int> Q; 17 memset(dis,-1,sizeof dis); 18 dis[1]=0; 19 Q.push(1); 20 while(!Q.empty()){ 21 int u=Q.front();Q.pop(); 22 if(u==n)return 1; 23 for(int i=1;i<=n;++i){ 24 if(~dis[i]||G[u][i]<=0)continue; 25 dis[i]=dis[u]+1; 26 Q.push(i); 27 } 28 } 29 return 0; 30 } 31 int dfs(int u,int low){ 32 int a=0; 33 if(u==n)return low; 34 for(int i=1;i<=n;++i) 35 if(G[u][i]>0&&dis[i]==dis[u]+1){ 36 a=dfs(i,min(low,G[u][i])); 37 G[u][i]-=a; 38 G[i][u]+=a; 39 if(a)return a; 40 } 41 return 0; 42 } 43 int dinic(){ 44 int ans=0,t; 45 while(BFS()) 46 while(t=dfs(1,0x3f3f3f3f))ans+=t; 47 return ans; 48 } 49 }D; 50 int main(){ 51 while(~scanf("%d%d",&m,&n)){ 52 D.build(); 53 printf("%d\n",D.dinic()); 54 } 55 return 0; 56 }
[USACO4.2]Drainage Ditches
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。