[洛谷 P4177][CEOI2008]order
转载请注明出处：http://danihao123.is-programmer.com/
啊啊啊只会做水题了……
很显然是最小割吧……长得很像最大权闭合子图，但又不一样的。
那么就把最大权闭合子图中的无穷边（我称之为违约边）的费用改成租用的费用。这样一来，如果选了计划（不割计划）还不购买机器（割去机器），那就只能支付租金了（割违约边）。
这其实也算是一种套路了吧？觉得以前见过很多次但是有很多叫法……
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #include <cstdio>#include <cstring>#include <cstdlib>#include <cctype>#include <utility>#include <algorithm>#include <queue>const int maxn = 200005;const int maxm = 2000005;const int maxe = maxm << 2;int n, m;int first[maxn];int next[maxe], to[maxe], flow[maxe], cap[maxe];int gcnt = 0;inline void add_edge(int u, int v, int f) { gcnt ++; next[gcnt] = first[u]; first[u] = gcnt; to[gcnt] = v; flow[gcnt] = 0; cap[gcnt] = f;}inline int rev(int i) { return (((i - 1) ^ 1) + 1);}inline void ins_edge(int u, int v, int f) { add_edge(u, v, f); add_edge(v, u, 0);} int d[maxn];int s, t, tot;inline bool bfs() { static bool vis[maxn]; std::fill(vis, vis + 1 + tot, false); std::fill(d, d + 1 + tot, 0); std::queue<int> Q; Q.push(s); vis[s] = true; d[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = first[u]; i; i = next[i]) { int v = to[i]; if(!vis[v] && cap[i] > flow[i]) { d[v] = d[u] + 1; vis[v] = true; Q.push(v); } } } return vis[t];}int cur[maxn];int dfs(int x, int a) { if(a == 0 || x == t) return a; int ans = 0; for(int &i = cur[x]; i; i = next[i]) { int v = to[i]; int f; if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) { ans += f; a -= f; flow[i] += f; flow[rev(i)] -= f; if(a == 0) break; } } if(a > 0) d[x] = -1; return ans;}int dinic() { int ans = 0; while(bfs()) { for(int i = 0; i <= tot; i ++) cur[i] = first[i]; ans += dfs(s, 0x7fffffff); } return ans;}int main() { int n, m; scanf("%d%d", &n, &m); s = 0; t = tot = n + m + 1; int ans = 0; for(int i = 1; i <= n; i ++) { int w, p; scanf("%d%d", &w, &p); ins_edge(s, i, w); ans += w; for(int j = 1; j <= p; j ++) { int id, co; scanf("%d%d", &id, &co); ins_edge(i, id + n, co); } } for(int i = n + 1; i <= n + m; i ++) { int co; scanf("%d", &co); ins_edge(i, t, co); } printf("%d\n", ans - dinic()); return 0;} |
评论 (0)
