本文主要是介绍hdu 1532——Drainage Ditches，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Dinic算法 数组版
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define INF 100001int G[205][205],dis[205];
int cur[205];
int n,m;int Min(int a,int b)
{if(a<b)return a;return b;
}int bfs()
{memset(dis,-1,sizeof(dis));queue<int> q;q.push(1);dis[1]=0;while(!q.empty()){int u=q.front();q.pop();for(int v=1;v<=n;v++)if(dis[v]==-1&&G[u][v]>0){dis[v]=dis[u]+1;q.push(v);}}if(dis[n]==-1)return 0;return 1;
}int dfs(int u,int flow)
{int d;int f=0;if(u==n||flow==0)return flow;for(int &v=cur[u];v<=n;v++)if(dis[v]==dis[u]+1&&G[u][v]>0&&(d=dfs(v,Min(flow,G[u][v])))){G[u][v]-=d;G[v][u]+=d;flow-=d;f+=d;} return f;
}int Dinic()
{int d;int ans=0;while(bfs()){for(int i=1;i<=n;i++)cur[i]=1;while((d=dfs(1,INF)))ans+=d;}return ans;
}int main()
{int u,v,c;while(~scanf("%d%d",&m,&n)){memset(G,0,sizeof(G)); for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&c);G[u][v]+=c;}printf("%d\n",Dinic());}return 0;
}
这篇关于hdu 1532——Drainage Ditches的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
