codes：
解決最大流問題參考代碼1：
1 #include <bits/stdc++.h>
2 #define MAX 1100
3 #define INF 0x3f3f3f3f
4 using namespace std;
5 struct Node{
6 int to;//終點
7 int cap;//容量
8 int rev;//反向邊
9 };
10
11 vector<Node> v[MAX];
12 bool visited[MAX];
13
14 void Add_Node(int from, int to, int cap)
15 {
16 v[from].push_back((Node){to,cap,v[to].size()});
17 v[to].push_back((Node){from,0,v[from].size()-1});
18 }
19
20 int DFS(int s, int t,int f)
21 {
22 if(s==t)
23 return f;
24 visited[s]=true;
25 for(int i=0;i<v[s].size();i++)
26 {
27 Node &temp=v[s][i];
28 if(visited[temp.to]==false &&temp.cap>0)
29 {
30 int d=DFS(temp.to,t,min(f,temp.cap));
31 if(d>0)
32 {
33 temp.cap-=d;
34 v[temp.to][temp.rev].cap+=d;
35 return d;
36 }
37 }
38 }
39 return 0;
40 }
41
42 int Max_Flow(int s,int t)
43 {
44 int flow=0;
45 for(;;)
46 {
47 memset(visited,false,sizeof(visited));
48 int f=DFS(s,t,INF);
49 if(f==0)
50 return flow;
51 flow+=f;
52 }
53 }
54 int main()
55 {
56 int n,s,t;
57 int start,over,capacity;
58 while(~scanf("%d%d%d",&n,&s,&t))
59 {
60 memset(v,0,sizeof(v));
61 for(int i=0;i<n;i++)
62 {
63 scanf("%d%d%d",&start,&over,&capacity);
64 Add_Node(start,over,capacity);
65 }
66 printf("%d\n",Max_Flow(s,t));
67 }
68 }
解決最大流問題參考代碼2：
1 #include <iostream>
2 #include <queue>
3 #include<string.h>
4 using namespace std;
5 #define arraysize 201
6 int maxData = 0x7fffffff;
7 int capacity[arraysize][arraysize]; //記錄殘留網絡的容量
8 int flow[arraysize]; //標記從源點到當前節點實際還剩多少流量可用
9 int pre[arraysize]; //標記在這條路徑上當前節點的前驅,同時標記該節點是否在隊列中
10 int n,m;
11 queue<int> myqueue;
12 int BFS(int src,int des)
13 {
14 int i,j;
15 while(!myqueue.empty()) //隊列清空
16 myqueue.pop();
17 for(i=1;i<=m;++i)
18 {
19 pre[i]=-1;
20 }
21 pre[src]=0;
22 flow[src]= maxData;//初始化為最大值
23 myqueue.push(src);
24 while(!myqueue.empty())
25 {
26 int index = myqueue.front();
27 myqueue.pop();
28 if(index == des) //找到了增廣路徑
29 break;
30 for(i=1;i<=m;++i)
31 {
32 if(i!=src && capacity[index][i]>0 && pre[i]==-1)
33 {
34 pre[i] = index; //記錄前驅!!!對應的是後繼
35 flow[i] = min(capacity[index][i],flow[index]); //關鍵：迭代的找到增量(change)
36 myqueue.push(i);//push進隊列
37 }
38 }
39 }
40 if(pre[des]==-1) //殘留圖中不再存在增廣路徑
41 return -1;
42 else
43 return flow[des];
44 }
45 int maxFlow(int src,int des)
46 {
47 int increasement= 0;
48 int sumflow = 0;
49 while((increasement=BFS(src,des))!=-1)
50 {
51 int k = des; //利用前驅尋找路徑
52 while(k!=src)
53 {
54 int last = pre[k];
55 capacity[last][k] -= increasement; //改變正向邊的容量
56 capacity[k][last] += increasement; //改變反向邊的容量
57 k = last;
58 }
59 sumflow += increasement;
60 }
61 return sumflow;
62 }
63 int main()
64 {
65 int i,j;
66 int start,end,ci;
67 while(cin>>n>>m)
68 {
69 memset(capacity,0,sizeof(capacity));
70 memset(flow,0,sizeof(flow));
71 for(i=0;i<n;++i)
72 {
73 cin>>start>>end>>ci;
74 if(start == end) //考慮起點終點相同的情況
75 continue;
76 capacity[start][end] +=ci; //此處注意可能出現多條同一起點終點的情況
77 }
78 cout<<maxFlow(0,m)<<endl;
79 }
80 return 0;
81 }
Blogs:
基礎知識博客：http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591573.html
模板博客提供：http://blog.csdn.net/y990041769/article/details/21026445
詳解博客（推薦）：http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html
詳解博客（推薦）：http://www.cnblogs.com/kuangbin/archive/2011/07/26/2117636.html
各種算法匯集博客：http://www.cnblogs.com/longdouhzt/archive/2012/05/20/2510753.html
