ZOJ 2314 Reactor Cooling——无源汇有上下界可行流

ZOJ 2314 Reactor Cooling——无源汇有上下界可行流

题意：判断一个图时候能构成无源汇有上下界可行流，是的话输出YES，并输出每条边的流量，不是的话输出NO

​

#include #include #include #include #include #include using namespace std;const int maxn = 500;const int INF = 0x3f3f3f3f;int n, m, s, t;struct Edge { int from, to, flow, cap, up, down;};struct Dinic { vector edges; vector G[maxn]; int level[maxn], cur[maxn]; void init() { edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int from , int to, int cap, int up, int down) { edges.push_back(Edge{from, to, 0, cap, up, down}); edges.push_back(Edge{to, from, 0, 0, up, down}); G[from].push_back(edges.size()-2); G[to].push_back(edges.size()-1); } int bfs() { memset(level, 0, sizeof(level)); level[s] = 1; queue q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap - e.flow > 0 && !level[e.to]) { level[e.to] = level[u] + 1; q.push(e.to); } } } return level[t]; } int dfs(int u, int f) { if (u == t || !f) return f; for (int &i = cur[u]; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap - e.flow > 0 && level[e.to] == level[u] + 1) { int d = dfs(e.to, min(f, e.cap - e.flow)); if (d > 0) { e.flow += d; edges[G[u][i]^1].flow -= d; return d; } } } return 0; } int maxflow() { int ans = 0, f; while (bfs()) { memset(cur, 0, sizeof(cur)); while ((f = dfs(s, INF))) ans += f; } return ans; }}ac;int A[maxn];int main() { int N; scanf("%d", &N); for (int kase = 1; kase <= N; kase++) { scanf("%d%d", &n, &m); s = 0, t = n+1; ac.init(); memset(A, 0, sizeof(A)); for (int i = 0; i < m; i++) { int d1, d2, d3, d4; scanf("%d%d%d%d", &d1, &d2, &d3, &d4); ac.addedge(d1, d2, d4 - d3, d4, d3); A[d1] -= d3; A[d2] += d3; } int sum = 0; for (int i = 1; i <= n; i++) { if (A[i] < 0) { ac.addedge(i, t, -A[i], 0, 0); sum -= A[i]; } else { ac.addedge(s, i, A[i], 0, 0); } } int ans = ac.maxflow(); if (kase != 1) printf("\n"); if (ans == sum) { printf("YES\n"); for (int i = 0, j = 0; j < m; i += 2, j++) { printf("%d\n", ac.edges[i].flow + ac.edges[i].down); } } else { printf("NO\n"); } } return 0;}

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