POJ_1273 Drainage Ditches 【网络流】

 1 //Edmonds-Karp
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <vector>
 5 #include <queue>
 6 #include <cstring>
 7 using namespace std;
 8 #define ll long long
 9 const int maxn = 2e2 + 13;
10 const int INF = 1e8 + 1;
11 int N, M;
12 int Flow[maxn]; //找到的最小的容量
13 int Pre[maxn];  //记录父节点
14 struct edge
15 {
16     //终点、容量、反边
17     int to, cap, rev;
18 };
19 int G[maxn][maxn];
20 void add_edge(int from, int to, int cap)
21 {
22     G[from][to] += cap;
23 }
24 
25 int BFS(int s, int t)
26 {
27     memset(Pre, -1, sizeof(Pre));
28     queue<int> Q;
29     Q.push(s);
30     Pre[s] = -1;
31     Flow[s] = INF;
32     while(!Q.empty())
33     {
34         int q = Q.front();
35         if(q == t)
36             break;
37         Q.pop();
38         for(int i = 1; i <= M; i++)
39         {
40             if(i != s && G[q][i] > 0 && Pre[i] == -1)
41             {
42                 Pre[i] = q;
43                 Flow[i] = min(Flow[q], G[q][i]);
44                 Q.push(i);
45             }
46         }
47     }
48     if(Pre[t] == -1)
49         return 0;
50     else
51         return Flow[t];
52 }
53 
54 ll EK(int s, int t)
55 {
56     ll ans = 0;
57     int f = BFS(s, t);
58     while(f)
59     {
60         ans += f;
61         int p = t;
62         while(Pre[p] != -1)
63         {
64             G[Pre[p]][p] -= f;
65             G[p][Pre[p]] += f;
66             p = Pre[p];
67         }
68         f = BFS(s, t);
69     }
70     return ans;
71 }
72 
73 int main()
74 {
75     freopen("input.txt", "r", stdin);
76     while(scanf("%d%d", &N, &M) != EOF)
77     {
78         memset(G, 0, sizeof(G));
79         int from, to, cap;
80         for(int i = 0; i < N; i++)
81         {
82             scanf("%d%d%d", &from, &to, &cap);
83             add_edge(from, to, cap);
84         }
85         printf("%I64d\n", EK(1, M));
86     }
87     return 0;
88 }

  1 //Dinic
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <vector>
  7 #include <queue>
  8 
  9 using namespace std;
 10 #define ll long long
 11 #define Min(a,b) ((a)>(b)?(b):(a))
 12 #define Max(a,b) ((a)>(b)?(a):(b))
 13 const int INF = 1e9;
 14 const int maxn = 5e2 + 13;
 15 struct edge
 16 {
 17     int to, cap, rev;
 18 };
 19 vector<edge> G[maxn];
 20 int N, M;
 21 int level[maxn], iter[maxn];
 22 //iter数组的作用就是记录DFS时该结点已经访问到的邻接点的位置
 23 void add_edge(int from, int to, int cap)
 24 {
 25     G[from].push_back( (edge){to, cap, G[to].size()});
 26     G[to].push_back( (edge){from, 0, G[from].size() - 1});
 27 }
 28 
 29 void BFS(int s)
 30 {
 31     memset(level, -1, sizeof(level));
 32     queue<int> que;
 33     level[s] = 0;
 34     que.push(s);
 35     while(!que.empty())
 36     {
 37         int v = que.front();
 38         que.pop();
 39         for(int i = 0; i < G[v].size(); i++)
 40         {
 41             edge &e = G[v][i];
 42             if(e.cap > 0 && level[e.to] < 0)
 43             {
 44                 level[e.to] = level[v] + 1;
 45                 que.push(e.to);
 46             }
 47         }
 48     }
 49 }
 50 
 51 int DFS(int s, int t, int f)
 52 {
 53     if(s == t)
 54         return f;
 55     for(int &i = iter[s]; i < G[s].size(); i++)
 56     {
 57         edge &e = G[s][i];
 58         if(e.cap > 0 && level[s] < level[e.to])
 59         {
 60             int d = DFS(e.to, t, Min(f, e.cap));
 61             if(d > 0)
 62             {
 63                 e.cap -= d;
 64                 G[e.to][e.rev].cap += d;
 65                 return d;
 66             }
 67         }
 68     }
 69     return 0;
 70 }
 71 
 72 int Dinic(int s, int t)
 73 {
 74     int flow = 0;
 75     while(1)
 76     {
 77         BFS(s);
 78         if(level[t] < 0)
 79             return flow;
 80         memset(iter, 0, sizeof(iter));
 81         int f = DFS(s, t, INF);
 82         while(f > 0)
 83         {
 84             flow += f;
 85             f = DFS(s, t, INF);
 86         }
 87     }
 88 }
 89 
 90 int main()
 91 {
 92     //freopen("input.txt", "r", stdin);
 93     int from, to, cap;
 94     while(~scanf("%d%d", &N, &M))
 95     {
 96         for(int i = 0; i < N; i++)
 97         {
 98             scanf("%d%d%d", &from, &to, &cap);
 99             add_edge(from, to, cap);
100         }
101         printf("%d\n", Dinic(1, M));
102         for(int i = 1; i < M; i++)
103         {
104             G[i].clear();
105         }
106     }
107     return 0;
108 }