SGU 194. Reactor Cooling(无源汇有上下界的网络流)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了SGU 194. Reactor Cooling(无源汇有上下界的网络流),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2560字,纯文字阅读大概需要4分钟。
内容图文
![SGU 194. Reactor Cooling(无源汇有上下界的网络流)](/upload/InfoBanner/zyjiaocheng/1221/d8550cc1ea0145a3adab29b8b6d6fc5c.jpg)
时间限制:0.5s
空间限制:6M
题意:
显然就是求一个无源汇有上下界的网络流的可行流的问题
Solution:
没什么好说的,直接判定可行流,输出就好了
code
/* 无汇源有上下界的网络流 */ #include <iostream> #include <cstring> #define ms(a,b) memset(a,b,sizeof a) usingnamespace std; constint MAXN = 209; struct node { int u, v, c, ne; } edge[MAXN * MAXN << 2]; int pHead[MAXN*MAXN], SS, ST, T, ncnt, ans; int Gup[MAXN][MAXN], Glow[MAXN][MAXN], st[MAXN], ed[MAXN], cap[MAXN][MAXN], tflow; void addEdge (int u, int v, int c) { edge[++ncnt].v = v, edge[ncnt].c = c, edge[ncnt].u = u; edge[ncnt].ne = pHead[u], pHead[u] = ncnt; edge[++ncnt].v = u, edge[ncnt].c = 0, edge[ncnt].u = v; edge[ncnt].ne = pHead[v], pHead[v] = ncnt; } int SAP (int pStart, int pEnd, int N) { int numh[MAXN], h[MAXN], curEdge[MAXN], pre[MAXN]; int cur_flow, flow_ans = 0, u, neck, i, tmp; ms (h, 0); ms (numh, 0); ms (pre, -1); for (i = 0; i <= N; i++) curEdge[i] = pHead[i]; numh[0] = N; u = pStart; while (h[pStart] <= N) { if (u == pEnd) { cur_flow = 1e9; for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) if (cur_flow > edge[curEdge[i]].c) neck = i, cur_flow = edge[curEdge[i]].c; for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) { tmp = curEdge[i]; edge[tmp].c -= cur_flow, edge[tmp ^ 1].c += cur_flow; } flow_ans += cur_flow; u = neck; } for ( i = curEdge[u]; i != 0; i = edge[i].ne) { if (edge[i].v > N) continue; //重要!!!if (edge[i].c && h[u] == h[edge[i].v] + 1) break; } if (i != 0) { curEdge[u] = i, pre[edge[i].v] = u; u = edge[i].v; } else { if (0 == --numh[h[u]]) continue; curEdge[u] = pHead[u]; for (tmp = N, i = pHead[u]; i != 0; i = edge[i].ne) { if (edge[i].v > N) continue; //重要!!!if (edge[i].c) tmp = min (tmp, h[edge[i].v]); } h[u] = tmp + 1; ++numh[h[u]]; if (u != pStart) u = pre[u]; } } return flow_ans; } int solve (int n) { SS = n + 1, ST = n + 2; for (int i = 1; i <= n; i++) { if (ed[i]) addEdge (SS, i, ed[i]); if (st[i]) addEdge (i, ST, st[i]); } int tem = SAP (SS, ST, ST); if (tem != tflow) return0; elsereturn1; } int n, m; int main() { ios::sync_with_stdio (0); ncnt = 1; cin >> n >> m; for (int i = 1, u, v, x, y; i <= m; i++) { cin >> u >> v >> x >> y; Gup[u][v] = y, Glow[u][v] = x; st[u] += x, ed[v] += x; tflow += x; addEdge (u, v, y - x); } if (solve (n) ) { cout << "YES\n"; for (int i = 2, x, y; i <= m * 2; i += 2) { x = edge[i].u, y = edge[i].v; cout << Gup[x][y]-edge[i].c << ‘\n‘; } } else cout << "NO\n"; return0; }
原文:http://www.cnblogs.com/keam37/p/4014284.html
内容总结
以上是互联网集市为您收集整理的SGU 194. Reactor Cooling(无源汇有上下界的网络流)全部内容,希望文章能够帮你解决SGU 194. Reactor Cooling(无源汇有上下界的网络流)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。