POJ 3801 Crazy Circuits——有源汇有上下界最小流

POJ 3801 Crazy Circuits——有源汇有上下界最小流

题意：给定n个点m条边，点的编号为1~n，另外有两个特殊的点+和-，+为原点，-为汇点，给定每条边的下限，问这个网络的最小流是多少？

思路：有源汇有有下界的最小流，​

#include #include #include #include #include #include #include using namespace std;const int maxn = 500;const int INF = 0x3f3f3f3f;struct Edge { int from, to, cap, flow;};struct Dinic { int n, m, s, t; vector edges; vector G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int n) { this->n = n; edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge{from, to, cap, 0}); edges.push_back(Edge{to, from, 0, 0}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int Maxflow(int s, int t) { this->s = s, this->t = t; int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; }}ac1, ac2;int sti(string x, int n) { if (x[0] == '+') return 0; else if (x[0] == '-') return n+1; else { int ans = 0; for (int i = 0; i < x.size(); i++) { ans = ans * 10 + (int)(x[i] - '0'); } return ans; }}int A[maxn];int main() { int n, m; while (~scanf("%d%d", &n, &m) && m && n) { ac1.init(n); ac2.init(n); memset(A, 0, sizeof(A)); int s = 0, t = n+1, ss = n+2, tt = n+3; string a, b; int c; for (int i = 1; i <= m; i++) { cin >> a >> b >> c; int u = sti(a, n); int v = sti(b, n); ac1.AddEdge(u, v, INF); A[u] -= c; A[v] += c; } ac1.AddEdge(t, s, INF); int sum = 0; for (int i = s; i <= t; i++) { if (A[i] < 0) { ac1.AddEdge(i, tt, -A[i]); sum -= A[i]; } else { ac1.AddEdge(ss, i, A[i]); } } int maxf = ac1.Maxflow(ss, tt); if (sum == maxf) { int ans1 = ac1.edges[m<<1].flow; for (int i = 0; i < m; i++) { int u = ac1.edges[i<<1].from, v = ac1.edges[i<<1].to; ac2.AddEdge(u, v, INF); } int ans2 = ac2.Maxflow(t, s); printf("%d\n", ans1 - ans2); } else { cout << "impossible" << endl; } } return 0;}

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