Power Network
水题
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> using namespace std; const int inf = 2e9; const int max_n = 200; const int max_m = 1e5; struct edge{ int to, cap, rev, next; }E[max_m * 2]; int head[max_n]; int cnt = 1; void add(int from, int to, int cap) { E[cnt].to = to; E[cnt].cap = cap; E[cnt].rev = cnt + 1; E[cnt].next = head[from]; head[from] = cnt++; E[cnt].to = from; E[cnt].cap = 0; E[cnt].rev = cnt - 1; E[cnt].next = head[to]; head[to] = cnt++; } int iter[max_n]; int dist[max_n]; bool searchpath(int s, int t) { fill(dist, dist + max_n, -1); queue<int> que;dist[s] = 0; que.push(s); while (!que.empty()) { int u = que.front();que.pop(); for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (dist[e.to] != -1 || e.cap == 0)continue; dist[e.to] = dist[u] + 1; que.push(e.to); } }return dist[t] != -1; } int matchpath(int u, int t, int f) { if (u == t)return f; for (int& i = iter[u];i;i = E[i].next) { edge& e = E[i]; if (dist[e.to] <= dist[u] || e.cap <= 0)continue; int d = matchpath(e.to, t, min(e.cap, f)); if (d > 0) { e.cap -= d; E[e.rev].cap += d; return d; } }return false; } int dinic(int s, int t) { int flow = 0;int f; while (searchpath(s, t)) { for (int i = 1;i < max_n;i++)iter[i] = head[i]; while (f = matchpath(s, t, inf)) flow += f; }return flow; } int n, np, nc, m; int main() { while (scanf("%d %d %d %d", &n, &np, &nc, &m) != EOF) { fill(head, head + n + 10, 0);cnt = 1; int start = n + 1;int ed = start + 1; for (int i = 1, u, v, c;i <= m;++i) { scanf(" (%d,%d)%d", &u, &v, &c); add(++u, ++v, c); }for (int i = 1, u, z;i <= np;++i) { scanf(" (%d)%d", &u, &z); add(start, ++u, z); }for (int i = 1, u, z;i <= nc;++i) { scanf(" (%d)%d", &u, &z); add(++u, ed, z); }printf("%d\n", dinic(start, ed)); } }
kuangbin题单刷题详解(网络流) 文章被收录于专栏
题单:https://vjudge.net/article/371