# 4.2.1 Drainage Ditches 草地排水

4.2.1 Drainage Ditches 草地排水

``````5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10``````

``````50
``````

``````#include <iostream>
using namespace std;

#define MAXN 210
#define inf 2100000000

int n,m;
int mat[MAXN][MAXN];
int source,sink;
int flow[MAXN][MAXN];

int max_flow()
{
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if(source == sink)
return inf;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; flow[i][j++] = 0);
for (; ;)
{
for(i = 1; i <= n; pre[i++] = 0);
pre[t = source] = source+1, d[t] = inf;
for(p = q = 0; p <= q && !pre[sink]; t = que[p++])
for(i = 1; i <= n; i++)
if(!pre[i] && (j = mat[t][i]-flow[t][i]))
pre[que[q++] = i] = t+1, d[i] = d[t] < j?d[t]:j;
else if(!pre[i] && (j = flow[i][t]))
pre[que[q++] = i] = -t-1, d[i] = d[t]<j?d[t]:j;
if(!pre[sink])
break;
for(i = sink; i != source;)
if(pre[i] > 0)
flow[pre[i]-1][i] += d[sink], i = pre[i]-1;
else
flow[i][-pre[i]-1] -= d[sink],i = -pre[i]-1;
}
for(j = 0, i = 1;i <= n; j += flow[source][i++]);
return j;
}

int main()
{
int i;
int s,e,c;
cin >> m >> n;
source = 1;
sink = n;
for(i = 1; i <= m; i++)
{
cin >> s >> e >> c;
mat[s][e] += c;
}
cout << max_flow() << endl;
return 0;
}``````

``````#include <iostream>
using namespace std;

#define MAXN 210
#define inf 2100000000

int n,m;
int mat[MAXN][MAXN];
int source,sink;
int flow[MAXN][MAXN];

int max_flow()
{
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if(source == sink)
return inf;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; flow[i][j++] = 0);
for (; ;)
{
for(i = 1; i <= n; pre[i++] = 0);
pre[t = source] = source+1, d[t] = inf;
for(p = q = 0; p <= q && !pre[sink]; t = que[p++])
for(i = 1; i <= n; i++)
if(!pre[i] && (j = mat[t][i]-flow[t][i]))
pre[que[q++] = i] = t+1, d[i] = d[t] < j?d[t]:j;
else if(!pre[i] && (j = flow[i][t]))
pre[que[q++] = i] = -t-1, d[i] = d[t]<j?d[t]:j;
if(!pre[sink])
break;
for(i = sink; i != source;)
if(pre[i] > 0)
flow[pre[i]-1][i] += d[sink], i = pre[i]-1;
else
flow[i][-pre[i]-1] -= d[sink],i = -pre[i]-1;
}
for(j = 0, i = 1;i <= n; j += flow[source][i++]);
return j;
}

int main()
{
int i;
int s,e,c;
cin >> m >> n;
source = 1;
sink = n;
for(i = 1; i <= m; i++)
{
cin >> s >> e >> c;
mat[s][e] += c;
}
cout << max_flow() << endl;
return 0;
}``````