题解 【P4177 [CEOI2008]order】

本题缺少 $\sum t_i$ 的范围，必须人肉二分数组大小才能通过，建议管理员加上。

最小割经典题。

首先不考虑租用，只考虑购买机器。最大流显然是凉了，所以考虑最小割。我们需要构造一个图，如果表示获得这个任务收益的边和表示购买所需要的机器的边都没有割掉，那么 $s,t$ 连通（$s$ 为源点，$t$ 为汇点）。

那么从源点 $s$ 向这些机器连边权为购买这个机器所需的费用的边，从机器向一个任务连边权为 INF 的边，从任务向汇点 $t$ 连一条边权为这个任务的收益的边。

其实以上是完全按照 P4313 文理分科 的套路连的边（（（

考虑租用。如果租用了机器我就不用买机器也能获得任务的受益了，所以机器向任务连的边并不是不可以割掉的，边权应该为这个任务租用这台机器的费用。

然后就完美解决了。数组开三百万能过。

#include <cstdio>
#include <queue>
#include <cstring>

const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, cap;
} e[3000005];
int head[10005], dep[10005], cur[10005], num[10005], tot = 1, s, t, n, m;
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap) {
	e[++ tot].to = v, e[tot].cap = cap, e[tot].nxt = head[u], head[u] = tot;
	e[++ tot].to = u, e[tot].cap = 0, e[tot].nxt = head[v], head[v] = tot;
}

void bfs() {
	memcpy(cur, head, sizeof cur);
	num[dep[t] = 1] = 1;
	Q.push(t);
	while (Q.size()) {
		int u = Q.front();
		Q.pop();
		for (int i = head[u]; i; i = e[i].nxt)
			if (!dep[e[i].to]) ++ num[dep[e[i].to] = dep[u] + 1], Q.push(e[i].to);
		
	}
}
int dfs(const int u, const int flow) {
	if (u == t) return flow;
	int used = 0, tmp = 0;
	for (int i = cur[u]; i; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && dep[u] - 1 == dep[e[i].to]) {
			tmp = dfs(e[i].to, min(e[i].cap, flow - used));
			used += tmp, e[i].cap -= tmp, e[i ^ 1].cap += tmp;
			if (used == flow) return used;
		}
	}
	cur[u] = head[u];
	if (!(-- num[dep[u]])) dep[s] = n + m + 2;
	++ num[++ dep[u]];
	return used;
}

int ISAP() {
	int Maxflow = 0;
	bfs();
	while (dep[s] <= n + m + 1) Maxflow += dfs(s, INF);
	return Maxflow;
}

int main() {
	int ans = 0;
	scanf("%d%d", &n, &m);
	s = 0, t = n + m + 1;
	for (int i = 1; i <= n; ++ i) {
		int x, T;
		scanf("%d%d", &x, &T);
		ans += x;
		AddEdge(i + m, t, x);
		while (T --) {
			int a, b;
			scanf("%d%d", &a, &b);
			AddEdge(a, i + m, b);
		}
	}
	for (int i = 1; i <= m; ++ i) {
		int x;
		scanf("%d", &x);
		AddEdge(s, i, x);
	}
	printf("%d\n", ans - ISAP());
	return 0;
}