Algorithm

USACO Section4.2 ditch

Problem Summary

Given a directed graph, a source and a sink, find the maximum flow from the source to the sink.

Solution

We can greedily build the network flow by iteratively adding flow. Each time, we use modified Dijkstra algorithm to find the maximal flow that can be added.

I use adjacency matrix to represent the graph, so the time complexity of this algorithm is O((N^2)*F), where F is the maximum flow.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
const int maxm = 202;
const int maxf = 10000000;
int n,m;
int cap[maxm][maxm];
int tot_flow=0;
int vis[maxm],flow[maxm],pre[maxm];
void get_max_flow()
{
	while(true)
	{
		memset(vis,0,sizeof(vis));
		memset(flow,0,sizeof(flow));
		flow[1]=maxf;
		while(true)
		{
			int max_flow=0;
			int max_loc=0;
			for(int i=1;i<=m;i++)
				if(!vis[i] && flow[i]>max_flow)
				{
					max_flow=flow[i];
					max_loc=i;
				}
			if(max_loc==0)
				break;
			vis[max_loc]=true;
			for(int i=1;i<=m;i++)
				if(!vis[i])
				{
					int tmp=min(max_flow,cap[max_loc][i]);
					if(flow[i]<tmp)
					{
						flow[i]=tmp;
						pre[i]=max_loc;
					}
				}
		}
		if(flow[m]==0) break;
		tot_flow+=flow[m];
		int i=m;
		while(i!=1)
		{
			int p=pre[i];
			cap[p][i]-=flow[m];
			cap[i][p]+=flow[m];
			i=p;
		}
	}
}
int main()
{
	fstream fin("ditch.in",ios::in);
	fstream fout("ditch.out",ios::out);
	fin>>n>>m;
	int s,e,c;
	for(int i=1;i<=n;i++)
	{
		fin>>s>>e>>c;
		cap[s][e]+=c;
	}
	get_max_flow();
	
	fout<<tot_flow<<endl;
	fin.close();
	fout.close();
	return 0;
}