Description
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Input
Output
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50 网络流Dinic模板
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = ;
int c[maxn][maxn];
int dep[maxn];
int cur[maxn];
int n,m;
void pt()
{
for (int i=;i<=n;++i){
for (int j=;j<=n;++j)
printf("%d ",c[i][j]);
printf("\n");
}
printf("==================\n");
}
int bfs (int s,int t)
{
memset(dep,-,sizeof dep);
queue<int> q;
while (!q.empty()) q.pop();
dep[s] = ;
q.push(s);
while (!q.empty()){
int u = q.front();
q.pop();
for (int v=;v<=n;++v){
if (c[u][v]>&&dep[v]==-){//能到达该节点的条件是这条边有流量,而且这个点没有被访问
dep[v] = dep[u]+;
q.push(v);
}
}
}
return dep[t]!=-;
}
int dfs (int u,int mi,int t)
{
if (u==t)
return mi;
int tmp;
for (int &v=cur[u];v<=n;++v){//
if (c[u][v]>&&dep[v]==dep[u]+&&(tmp=dfs(v,min(mi,c[u][v]),t))){//下一节点的深度是当前节点+1
c[u][v]-=tmp;
c[v][u]+=tmp;
return tmp;
}
}
return ;//别忘写返回0!!!
}
int dinic ()
{
int ans = ;
int tmp;
while (bfs(,n)){//每次按照深度建立分层图,这样每次dfs的时候下一节点的深度是当前节点+1
while (){
for (int i=;i<maxn;++i) cur[i]=;//当前弧优化
tmp = dfs(,inf,n);
//printf("%d\n",tmp);
if (tmp==)
break;
//pt();
ans+=tmp;
}
}
return ans;
}
int main()
{
//freopen("de.txt","r",stdin);
while (~scanf("%d%d",&m,&n)){
memset(c,,sizeof c);
for (int i=;i<m;++i){
int u,v,cap;
scanf("%d%d%d",&u,&v,&cap);
c[u][v]+=cap;
}
printf("%d\n",dinic());
}
return ;
}
#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <queue>#include <string>#include <cstring>using namespace std;const int inf = 0x3f3f3f3f;const int maxn = 220;int c[maxn][maxn];int dep[maxn];int cur[maxn];int n,m;void pt(){ for (int i=1;i<=n;++i){ for (int j=1;j<=n;++j) printf("%d ",c[i][j]); printf("\n"); } printf("==================\n");}int bfs (int s,int t){ memset(dep,-1,sizeof dep); queue<int> q; while (!q.empty()) q.pop(); dep[s] = 0; q.push(s); while (!q.empty()){ int u = q.front(); q.pop(); for (int v=1;v<=n;++v){ if (c[u][v]>0&&dep[v]==-1){//能到达该节点的条件是这条边有流量,而且这个点没有被访问 dep[v] = dep[u]+1; q.push(v); } } } return dep[t]!=-1;}int dfs (int u,int mi,int t){ if (u==t) return mi; int tmp; for (int &v=cur[u];v<=n;++v){// if (c[u][v]>0&&dep[v]==dep[u]+1&&(tmp=dfs(v,min(mi,c[u][v]),t))){//下一节点的深度是当前节点+1 c[u][v]-=tmp; c[v][u]+=tmp; return tmp; } } return 0;//别忘写返回0!!!}int dinic (){ int ans = 0; int tmp; while (bfs(1,n)){//每次按照深度建立分层图,这样每次dfs的时候下一节点的深度是当前节点+1 while (1){ for (int i=0;i<maxn;++i) cur[i]=1;//当前弧优化 tmp = dfs(1,inf,n); //printf("%d\n",tmp); if (tmp==0) break; //pt(); ans+=tmp; } } return ans;}int main(){ //freopen("de.txt","r",stdin); while (~scanf("%d%d",&m,&n)){ memset(c,0,sizeof c); for (int i=0;i<m;++i){ int u,v,cap; scanf("%d%d%d",&u,&v,&cap); c[u][v]+=cap; } printf("%d\n",dinic()); } return 0;}