性质,巨大多性质。
设 \(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;
}
标签:cnt,ARC142E,int,res,wei,flow,head
From: https://www.cnblogs.com/Kobe303/p/16852818.html