首页 > 代码库 > SGU 194. Reactor Cooling(无源汇有上下界的网络流)
SGU 194. Reactor Cooling(无源汇有上下界的网络流)
时间限制:0.5s
空间限制:6M
题意:
显然就是求一个无源汇有上下界的网络流的可行流的问题
Solution:
没什么好说的,直接判定可行流,输出就好了
code
/* 无汇源有上下界的网络流*/#include <iostream>#include <cstring>#define ms(a,b) memset(a,b,sizeof a)using namespace std;const int 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) return 0; else return 1;}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"; return 0;}
SGU 194. Reactor Cooling(无源汇有上下界的网络流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。