USACO Drainage Ditches 发表于 2016-05-10 | 分类于 USACO Training , Chapter 4 Advanced algorithms and difficult drills , Section 4.2 | Code123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155/* ID: wcr19961 PROG: ditch LANG: C++11*/#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const int inf = 0x3f3f3f3f;const int maxn = 210;struct Edge { int from, to, cap, flow; Edge(int from, int to, int cap, int flow) : from(from), to(to), cap(cap), flow(flow) {}};bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to);}struct ISAP { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 int p[maxn]; // 可增广路上的上一条弧 int num[maxn]; // 距离标号计数 void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof vis); queue<int> Q; Q.push(t); vis[t] = 1; d[t] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]^1]; if(!vis[e.from] && e.cap > e.flow) { vis[e.from] = 1; d[e.from] = d[x] + 1; Q.push(e.from); } } } return vis[s]; } void ClearAll(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void ClearFlow() { for(int i = 0; i < edges.size(); i++) edges[i].flow = 0; } int Augment() { int x = t, a = inf; while(x != s) { Edge& e = edges[p[x]]; a = min(a, e.cap-e.flow); x = edges[p[x]].from; } x = t; while(x != s) { edges[p[x]].flow += a; edges[p[x]^1].flow -= a; x = edges[p[x]].from; } return a; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; BFS(); memset(num, 0, sizeof(num)); for(int i = 0; i < n; i++) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { flow += Augment(); x = s; } int ok = 0; for(int i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to] + 1) { // Advance ok = 1; p[e.to] = G[x][i]; cur[x] = i; // 注意 x = e.to; break; } } if(!ok) { // Retreat int m = n-1; // 初值注意 for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow && d[e.to] != -1) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m+1]++; cur[x] = 0; // 注意 if(x != s) x = edges[p[x]].from; } } return flow; } vector<int> Mincut() { // call this after maxflow BFS(); vector<int> ans; for(int i = 0; i < edges.size(); i++) { Edge& e = edges[i]; if(!vis[e.from] && vis[e.to] && e.cap > 0) ans.push_back(i); } return ans; } void Reduce() { for(int i = 0; i < edges.size(); i++) edges[i].cap -= edges[i].flow; }} isap;int main() { freopen("ditch.in", "r", stdin); freopen("ditch.out", "w", stdout); int n, m, u, v, len; scanf("%d%d", &m, &n); isap.ClearAll(n + 1); for (int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &len); isap.AddEdge(u, v, len); } printf("%d\n", isap.Maxflow(1, n)); return 0;}