ARC142E

性质，巨大多性质。

设 \(mn_x=\max\limits_{(x,y)\in E}\left\{\min(b_x,b_y)\right\}\)，首先让 \(a_i\to mn_i\)（如果不够）。

关键性质：记 \(X\) 表示所有 \(b_x\gt a_x\) 的集合，\(Y=\left\{1,\cdots,n\right\}\setminus X\)。那么对于一条边，至少有一个点属于 \(Y\)。

也就是说，如果一条边 \((x,y)\) 不满足条件，假设 \(x\in X\)，我们让它合法的条件就是要么使得 \(a_x\to b_x\)，要么使得 \(a_y\to b_x\)。

记 \(S\) 为源点，\(T\) 为汇点，\((u,v,w)\) 表示网络中 \(u\to v\) 容量为 \(w\) 的边。

考虑网络流建图：

• \(i\in X,(S,i,b_i-a_i)\)
• \(i\in Y,j\in[1,100],((i,j),T,1)\)
• \(i\in Y,j\in[2,100],((i,j),(i,j-1),\infty)\)
• \((x,y)\in E,x\in X,y\in Y,(x,(y,b_x-a_y),\infty)\)，如果 \(a_y\lt b_x\)。

其中 \((i,j)\) 表示一类特殊的点，共 \(100n\) 个。

这样建图之后跑一遍最小割就是答案。

Code：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N = 105, inf = 0x3f3f3f3f;
namespace F {
	const int N = 20005, M = N * 20;
	
	int S, T;
	int head[N], now[N], ver[M], wei[M], nxt[M], cnt = 1;
	int d[N];
	
	void add(int u, int v, int w) {
		ver[++cnt] = v, wei[cnt] = w, nxt[cnt] = head[u], head[u] = cnt;
		ver[++cnt] = u, wei[cnt] = 0, nxt[cnt] = head[v], head[v] = cnt;
	}
	
	queue <int> q;
	
	bool bfs() {
		memset(d, 0, sizeof d), d[S] = 1;
		now[S] = head[S]; 
		while (q.size()) q.pop(); q.push(S);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = head[u]; i; i = nxt[i]) {
				int v = ver[i], w = wei[i];
				if (w && !d[v]) {
					d[v] = d[u] + 1, now[v] = head[v], q.push(v);
					if (v == T) return true;
				}
			}
		}
		return false;
	}
	
	int dinic(int u, int flow) {
		if (u == T) return flow;
		int res = flow;
		for (int &i = now[u]; i; i = nxt[i]) {
			int v = ver[i], w = wei[i];
			if (w && d[v] == d[u] + 1) {
				int k = dinic(v, min(res, w));
				if (!k) d[v] = 0;
				wei[i] -= k, wei[i ^ 1] += k, res -= k;
			}
			if (!res) break;
		}
		return flow - res;
	}
	
	ll maxflow() {
		ll res = 0; int flow;
		while (bfs())
			while (flow = dinic(S, inf)) res += flow;
		return res;
	}
}

int n, m;
int a[N], b[N], mn[N];
int ans;
vector <int> G[N];
bool flag[N];

void chkmax(int &a, int b) { if (a < b) a = b; }

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]);
	scanf("%d", &m);
	for (int i = 1, u, v; i <= m; ++i) scanf("%d%d", &u, &v), G[u].pb(v), G[v].pb(u), chkmax(mn[u], min(b[u], b[v])), chkmax(mn[v], min(b[u], b[v]));
	for (int i = 1; i <= n; ++i) if (a[i] < mn[i]) ans += mn[i] - a[i], a[i] = mn[i];
	for (int i = 1; i <= n; ++i) if (a[i] < b[i]) flag[i] = 1;
	F::S = 0, F::T = n * 101 + 1;
	for (int x = 1; x <= n; ++x) {
		if (flag[x]) {
			F::add(F::S, x, b[x] - a[x]);
			for (auto y : G[x])
				if (!flag[y] && b[x] > a[y]) F::add(x, n + 100 * (y - 1) + (b[x] - a[y]), inf);
		}
		else {
			for (int i = 1; i <= 100; ++i) {
				F::add(n + 100 * (x - 1) + i, F::T, 1);
				if (i > 1) F::add(n + 100 * (x - 1) + i, n + 100 * (x - 1) + i - 1, inf);
			}
		}
	}
	printf("%lld", ans + F::maxflow());
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16852818.html