HDU 1532 Drainage Ditches——最大流EK算法

HDU 1532 Drainage Ditches——最大流EK算法

模板题

#include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1000 + 10;struct Node { int to; int cap; int rev;};vector v[maxn];bool used[maxn];void add_node(int from, int to, int cap) { v[from].push_back((Node){to, cap, v[to].size()}); v[to].push_back((Node){from, 0, v[from].size() - 1});}int dfs(int s, int t, int f) { if (s == t) return f; used[s] = true; for (int i = 0; i < v[s].size(); i++) { Node &temp = v[s][i]; if (used[temp.to] == false && temp.cap > 0) { int d = dfs(temp.to, t, min(f, temp.cap)); if (d > 0) { temp.cap -= d; v[temp.to][temp.rev].cap += d; return d; } } } return 0;}int max_flow(int s, int t) { int flow = 0; while (true) { memset(used, false, sizeof(used)); int f = dfs(s, t, INF); if (f == 0) return flow; flow += f; }}int main(){ int n, m; while (scanf("%d %d", &n, &m) == 2) { memset(v, 0, sizeof(v)); for (int i = 0; i < n; i++) { int x, y, z; scanf("%d %d %d", &x, &y, &z); add_node(x, y, z); } printf("%d\n", max_flow(1, m)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。