首页 > 代码库 > Drainage Ditches
Drainage Ditches
题目链接
- 题意:
n个点,m条边,求1点到n点的最大流
N (0 <= N <= 200) and M (2 <= M <= 200).
struct Edge { int from, to, cap, flow; bool operator< (const Edge& rhs) const { return from < rhs.from || (from == rhs.from && to < rhs.to); } }; const int MAXV = 210; struct ISAP { int n, m, s, t; vector<Edge> edges; vector<int> G[MAXV]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[MAXV]; // BFS使用 int d[MAXV]; // 从起点到i的距离 int cur[MAXV]; // 当前弧指针 int p[MAXV]; // 可增广路上的上一条弧 int num[MAXV]; // 距离标号计数 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(); REP(i, G[x].size()) { 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; REP(i, n) G[i].clear(); edges.clear(); } void ClearFlow() { REP(i, edges.size()) 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, int need) { this->s = s; this->t = t; int flow = 0; BFS(); memset(num, 0, sizeof(num)); REP(i, n) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { flow += Augment(); if(flow >= need) return flow; x = s; } int ok = 0; FF(i, cur[x], G[x].size()) { 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; // 初值注意 REP(i, G[x].size()) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow) 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; REP(i, edges.size()) { Edge& e = edges[i]; if(!vis[e.from] && vis[e.to] && e.cap > 0) ans.push_back(i); } return ans; } void Reduce() { REP(i, edges.size()) edges[i].cap -= edges[i].flow; } void print() { printf("Graph:\n"); REP(i, edges.size()) printf("%d->%d, %d, %d\n", edges[i].from, edges[i].to , edges[i].cap, edges[i].flow); } } mf; int main() { int n, m, a, b, v; while (~RII(m, n)) { mf.ClearAll(n); REP(i, m) { RIII(a, b, v); a--; b--; mf.AddEdge(a, b, v); } WI(mf.Maxflow(0, n - 1, INF)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。