UVA 820 Internet Bandwidth——最大流

UVA 820 Internet Bandwidth——最大流

裸题

#include #include #include #include #include #include using namespace std;const int maxn = 500;const int INF = 0x3f3f3f3f;struct Edge { int to, cap, rev; Edge(int x=0, int y=0, int z=0) : to(x), cap(y), rev(z) {}};vector G[maxn];int level[maxn], iter[maxn];void addedge(int u, int v, int cap) { G[u].push_back(Edge(v, cap, G[v].size())); G[v].push_back(Edge(u, 0, G[u].size()-1));}void bfs(int s) { memset(level, -1, sizeof(level)); queue q; level[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (int i = 0; i < G[v].size(); i++) { Edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } }}int dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < G[v].size(); i++) { Edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0;}int max_flow(int s, int t) { int flow = 0; while (true) { bfs(s); if (level[t] < 0) return flow; memset(iter, 0, sizeof(iter)); int f; while ((f = dfs(s, t, INF)) > 0) flow += f; }}int kase = 0, n, s, t, m, u, v, c;int main() { while (~scanf("%d", &n) && n) { for (int i = 0; i < maxn; i++) G[i].clear(); scanf("%d %d %d", &s, &t, &m); while (m--) { scanf("%d %d %d", &u, &v, &c); addedge(u, v, c); addedge(v, u, c); } printf("Network %d\nThe bandwidth is %d.\n\n", ++kase, max_flow(s, t)); } return 0;}

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