P4177 [CEOI2008]order 网络流，最小割，最大权闭合子图

如果没有租用机器就是一个裸的最大权闭合子图。现在有了租用机器应该怎么办呢？

单独拆点是不行的，因为会和直接买下的情况脱离关系，租借是和连边直接相关的，那么就可以考虑在边上下功夫。我们把从工程到机器的连边从(INF)变成租用费用，这样再跑最大权闭合子图，就可以同时考虑租用费用了。如果租用费用过高就会割断（选用）购买机器的费用，反之亦然。

#include <bits/stdc++.h>
using namespace std;

const int N = 2410;
const int M = 4000010;
const int INF = 0x3f3f3f3f;

struct Graph {
	int cnt, head[N];

	struct edge {
		int nxt, to, f;
	}e[M];

	void Init () {
		cnt = -1;
		memset (head, -1, sizeof (head));
	}

	void add_len (int u, int v, int f) {
		e[++cnt] = (edge) {head[u], v, f}; head[u] = cnt;
		e[++cnt] = (edge) {head[v], u, 0}; head[v] = cnt;
	}

	queue <int> q;
	int cur[N], deep[N];
	
	bool bfs (int s, int t) {
		memcpy (cur, head, sizeof (head));
		memset (deep, 0x3f, sizeof (deep));
		deep[s] = 0; q.push (s);
		while (!q.empty ()) {
			int u = q.front (); q.pop ();
			for (int i = head[u]; ~i; i = e[i].nxt) {
				int v = e[i].to;
				if (deep[v] == INF && e[i].f) {
					deep[v] = deep[u] + 1;
					q.push (v);
				}
			}
		}
		return deep[t] != INF;
	}

	int dfs (int u, int t, int lim) {
		if (u == t || !lim) return lim;
		int tmp = 0, flow = 0;
		for (int &i = cur[u]; ~i; i = e[i].nxt) {
			int v = e[i].to;
			if (deep[v] == deep[u] + 1) {
				tmp = dfs (v, t, min (lim, e[i].f));
				lim -= tmp;
				flow += tmp;
				e[i ^ 0].f -= tmp;
				e[i ^ 1].f += tmp;
				if (!lim) break;
			}
		}
		return flow;
	}
	
	int Dinic (int s, int t) {
		int min_cut = 0;
		while (bfs (s, t)) {
			min_cut += dfs (s, t, INF);
		}
		return min_cut;
	}
}G;

int n, m;

int A (int x) {return n * 0 + x;}
int B (int x) {return n * 1 + x;}

int main () {
	//freopen ("data.in", "r", stdin);
	cin >> n >> m; G.Init ();
	int s = N - 1, t = N - 2, ans = 0;
	for (int i = 1; i <= n; ++i) {
		static int w, k, p, r;
		cin >> w >> k; ans += w;
		G.add_len (s, A (i), w); //get_val = w
		for (int j = 1; j <= k; ++j) {
			cin >> p >> r;
			G.add_len (A (i), B (p), r); //rent cost = r
		}
	}
	for (int i = 1; i <= m; ++i) {
		static int w; cin >> w;
		G.add_len (B (i), t, w);
	}
	cout << ans - G.Dinic (s, t) << endl;
}

P4177 [CEOI2008]order 网络流，最小割，最大权闭合子图

相关推荐