HYSBZ 3876 支线剧情——有上下界的费用流

HYSBZ 3876 支线剧情——有上下界的费用流

题意：中文题意，总而言之就是每条边都要被经过

思路：把需要被覆盖的边的下界设为1，然后根据题意每个点（除1）向1连边，这样就形成了一个无源汇的图，首先给每条边一个流量，值为它的下界，构成一个初始流，求这个初始流的费用，然后 在这个图的残余网络上建立ss和tt跑费用流，求得的值加上之前初始流的值就是结果

#include #include #include #include #include #include using namespace std;const int maxn = 500;const int INF = 0x3f3f3f3f;struct Edge { int from, to, cap, flow, cost;};struct MCMF { int m, s, t; vector edges; vector G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap, int cost) { edges.push_back((Edge){from, to, cap, 0, cost}); edges.push_back((Edge){to, from, 0, 0, -cost}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s, int t, int &flow, int &cost) { for (int i = 0; i < maxn; i++) d[i] = INF; memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0, a[s] = INF; queue Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap > e.flow && d[e.to] > d[u] + e.cost) { d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } } } } if (d[t] == INF) return false; flow += a[t]; cost += d[t] * a[t]; int u = t; while (u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return true; } int Mincost(int s, int t) { int flow = 0, cost = 0; while (BellmanFord(s, t, flow, cost)); return cost; }}ac1;int A[maxn];int main() { int n; scanf("%d", &n); ac1.init(); memset(A, 0, sizeof(A)); int ss = 0, tt = n+1, sum = 0; for (int i = 1; i <= n; i++) { int cnt; scanf("%d", &cnt); for (int j = 1; j <= cnt; j++) { int a, b; scanf("%d%d", &a, &b); ac1.AddEdge(i, a, INF, b); A[i] -= 1; A[a] += 1; sum += b; } } for (int i = 2; i <= n; i++) { ac1.AddEdge(i, 1, INF, 0); } for (int i = 1; i <= n; i++) { if (A[i] < 0) { ac1.AddEdge(i, tt, -A[i], 0); } else { ac1.AddEdge(ss, i, A[i], 0); } } printf("%d\n", ac1.Mincost(ss, tt) + sum); return 0;}

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