题解【NKOJ8317 最大分值】

何老板给你一个连通无向简单图。图中有 $n$ 个点和 $m$ 条边。点编号 $1$ 到 $n$，边编号 $1$ 到 $m$。
每个点有 $A,B$ 两个分值，$i$ 号点的分值表示为 $A_i$ 和 $B_i$。

何老板想要删掉图中若干个点，删掉 $i$ 号点，需要耗费 $A_i$ 分。当一个点被删掉，与之相连的边也会被删掉。
删掉若干点后，剩余图的得分计算方法如下：
对于一个连通块，得分为块中所有点的 $B$ 属性值总和的绝对值。
图的总得分为所有连通块得分的总和。

设删点耗费的总分值为 $SumA$，剩下的图的总得分为 $SumB$。
何老板想知道，$SumB-SumA$ 的最大值是多少，请你帮忙计算。

$1\le n,m\le 300,1\le A_i\le 10^6,-10^6\le B_i\le 10^6$

---

每个连通块的贡献为 $\lvert\sum B_i\rvert=\max(\sum B_i,-\sum B_i)$。

如果要单独计算每个点的贡献，那么它必须满足如果它的贡献是 $B_i$，与它在一个连通块中的所有点都是 $B_i$；如果它的贡献是 $-B_i$，与它在一个连通块中的所有点都是 $-B_i$。

考虑最小割。把每个点拆成 $i$ 和 $i^{\prime}$，从源点 $S$ 向每个点 $i$ 连边，容量为 $B_i$，从 $i$ 向 $i^{\prime}$ 连边，容量为 $A_i$。从 $i^{\prime}$ 向汇点 $T$ 连边，容量为 $-B_i$

那么现在的问题是如何满足上面提到的限制。若存在边 $u\leftrightarrow v$，从 $u^{\prime}$ 向 $v$ 连边，容量为 $+\infty$，从 $v^{\prime}$ 向 $u$ 连边，容量为 $+\infty$。

这样的话跑一遍最小割我们求出来的到底是什么呢？

我们算的相当于是 $-\lvert\sum B_i\rvert=\min(\sum B_i,-\sum B_i)$，然后还要加上 $\sum A_i$，也就是说算出来的是 $SumA-SumB$ 的最小值，正好是原问题的相反数。

然而图中有容量为负数的边，这是不好的，我劝出题人耗子尾汁，好好反思（

其实只需要分类讨论一下就行了。

若 $B_i>0$，那么我们假设这个点对答案的贡献是 $-B_i$，先把 $ans$ 加上 $-B_i$，然后 $S$ 到 $i$ 的边容量改为 $2\times B_i$， $i$ 到 $i^{\prime}$ 的边容量改为 $A_i+B_i$，$i^{\prime}$ 到 $T$ 的边不连。$B_i<0$ 同理，最终答案即为 $ans$ 减去最小割。

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

typedef std::pair<int, int> PII;
const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
int n, m, k;
bool selected[100005];

struct Graph {
	struct Edge {
		int to, nxt, cap;
	} e[500005];
	int head[50005], dep[50005], cur[50005], num[50005], tot, s, t;
	std::queue<int> Q;
	void clear() {
		memset(head, 0, sizeof head);
		tot = 1;
	}
	inline void AddEdge(int u, int v, 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);
		memset(dep, 0, sizeof dep);
		memset(num, 0, sizeof num);
		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(int u, 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] = t + 1;
		++ num[++ dep[u]];
		return used;
	}
	
	int ISAP() {
		int Maxflow = 0;
		bfs();
		while (dep[s] <= t) Maxflow += dfs(s, INF);
		return Maxflow;
	}
} G;

int A[305];

int main() {
	G.tot = 1;
	int n, m, ans = 0;
	scanf("%d%d", &n, &m);
	G.s = 0, G.t = 2 * n + 1;
	for (int i = 1; i <= n; ++ i) scanf("%d", A + i);
	for (int i = 1; i <= n; ++ i) {
		int x;
		scanf("%d", &x);
		if (x >= 0) {
			G.AddEdge(G.s, i, 2 * x);
			G.AddEdge(i, i + n, A[i] + x);
			ans += x;
		} else {
			G.AddEdge(i, i + n, A[i] - x);
			G.AddEdge(i + n, G.t, -2 * x);
			ans -= x;
		}
	}
	for (int i = 1; i <= m; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G.AddEdge(u + n, v, INF);
		G.AddEdge(v + n, u, INF);
	}
	printf("%d", ans - G.ISAP());
}