正文
CF704D Captain America（上下界网络流）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
传送门
题意：
二维平面给出\(n\)个点，现在可以给每个点进行染色，染红色的代价为\(r\)，染蓝色的代价为\(b\)。
之后会有\(m\)个限制，形式如：\(t_i\ l_i\ d_i\)，当\(t_i=1\)时，表示\(l_i\)行两种颜色的点数相差不超过\(d_i\)；类似地，当\(t_i=2\)时表示的是列时的状态。
问最终怎么染色代价最小且符合限制条件。
思路：
- 带上下界的网络流。
- 我们不妨设\(r<b\)，那么肯定是红点越多越好。我们找准最大这个数量关系，然后考虑最大流。
- 建图方式为：左右两排分别表示行和列，中间则为每个点，源点和左排相连带有上下界，汇点和右排相连带有上下界。
- 上下界很好推，假设第\(i\)行共\(tot_i\)个点，我们选\(x\)个红点，那么就有：\(|x-(tot - x)|\leq d\)，绝对值打开化简即可得到\(x\)的范围，若一个满足范围，另一个点也必然满足范围。
- 为什么要在两排中间加上点？因为我们最后要输出方案，我们需要根据流过点的流量来判断这个点是否染色。
这种有源有汇最大流，首先转化为无源无汇最大流，得到\(s\)到\(t\)的可行流，最后去掉附加点和边，最后再从\(s\)到\(t\)跑一次最大流，两次的答案加起来即可得到答案。
注意进入流量若大于出度流量，我们连接源点向它来补充这多出来的。
详见代码：
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 5e5 + 5;
#define INF 0x3f3f3f3f
int s, t, SS, TT;
int n, m, r, b, f;
void Fail() {
cout << -1 << '\n';
exit(0);
}
template <class T>
struct Dinic{
struct Edge{
int v, next;
T flow;
Edge(){}
Edge(int v, int next, T flow) : v(v), next(next), flow(flow) {}
}e[N << 1];
int head[N], tot;
int dep[N], M[N];
int all;
void init() {
memset(head, -1, sizeof(head)); tot = 0;
}
void adde(int u, int v, T down, T up) {
if(up < down) Fail();
e[tot] = Edge(v, head[u], up - down);
head[u] = tot++;
e[tot] = Edge(u, head[v], 0);
head[v] = tot++;
M[u] -= down; M[v] += down;
}
void adde() {
for(int i = 0; i <= t; i++) {
if(M[i] > 0) adde(SS, i, 0, M[i]);
else if(M[i] < 0) adde(i, TT, 0, -M[i]);
}
adde(t, s, 0, INF);
}
bool BFS(int _S, int _T) {
memset(dep, 0, sizeof(dep));
queue <int> q; q.push(_S); dep[_S] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
if(!dep[v] && e[i].flow > 0) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[_T] != 0;
}
T dfs(int _S, int _T, T a) {
T flow = 0, f;
if(_S == _T || a == 0) return a;
for(int i = head[_S]; ~i; i = e[i].next) {
int v = e[i].v;
if(dep[v] != dep[_S] + 1) continue;
f = dfs(v, _T, min(a, e[i].flow));
if(f) {
e[i].flow -= f;
e[i ^ 1].flow += f;
flow += f;
a -= f;
if(a == 0) break;
}
}
if(!flow) dep[_S] = -1;
return flow;
}
T dinic(int _S, int _T) {
T max_flow = 0;
while(BFS(_S, _T)) max_flow += dfs(_S, _T, INF);
return max_flow;
}
T work() {
int tmp = dinic(SS, TT);
for(int i = head[SS]; i != -1; i = e[i].next) {
if(e[i].flow) Fail();
}
int ans = e[tot - 1].flow;
e[tot - 1].flow = e[tot - 2].flow = 0;
for(int i = head[SS]; i != -1; i = e[i].next) {
e[i].flow = e[i ^ 1].flow = 0;
}
for(int i = head[TT]; i != -1; i = e[i].next) {
e[i].flow = e[i ^ 1].flow = 0;
}
ans += dinic(s, t);
return ans;
}
//f = 1 -> r > b;
void Print(int f, int L, int R) {
for(int i = L + 1; i <= L + n; i++) {
bool flag = false;
for(int j = head[i]; j != -1; j = e[j].next) {
int v = e[j].v;
if(e[j].flow == 0 && v > n + L && v <= n + L + R) {
flag = true;
cout << (f == 1 ? 'b' : 'r');
}
}
if(!flag) cout << (f == 1 ? 'r' : 'b');
}
}
};
Dinic <int> solver;
int x[N], y[N], X[N], Y[N];
int mxx[N], mxy[N], cntx[N], cnty[N];
void Hash(int *a, int *b, int &c) {
sort(b + 1, b + n + 1);
c = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + c + 1, a[i]) - b;
}
void Hash(int &a, int &b) {
Hash(x, X, a); Hash(y, Y, b);
}
void run() {
cin >> r >> b;
if(r >= b) {
f = 1;
swap(r, b);
}
solver.init();
for(int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
X[i] = x[i], Y[i] = y[i];
}
int lx, ly;
Hash(lx, ly);
dbg(lx, ly);
s = 0, t = lx + ly + n + 1;
SS = t + 1, TT = t + 2;
for(int i = 1; i <= n; i++) {
solver.adde(x[i], lx + i, 0, 1);
solver.adde(lx + i, y[i] + n + lx, 0, 1);
}
for(int i = 1; i <= lx; i++) mxx[i] = n;
for(int i = 1; i <= ly; i++) mxy[i] = n;
for(int i = 1; i <= m; i++) {
int t, l, d; cin >> t >> l >> d;
if(t & 1) {
int p = lower_bound(X + 1, X + lx + 1, l) - X;
if(X[p] != l) continue;
else mxx[p] = min(mxx[p], d);
}
else {
int p = lower_bound(Y + 1, Y + ly + 1, l) - Y;
if(Y[p] != l) continue;
else mxy[p] = min(mxy[p], d);
}
}
for(int i = 1; i <= n; i++) ++cntx[x[i]];
for(int i = 1; i <= n; i++) ++cnty[y[i]];
for(int i = 1; i <= lx; i++) {
if(cntx[i] <= mxx[i]) solver.adde(s, i, 0, INF);
else solver.adde(s, i, (cntx[i] - mxx[i] + 1) / 2, (cntx[i] + mxx[i]) / 2);
}
for(int i = 1; i <= ly; i++) {
if(cnty[i] <= mxy[i]) solver.adde(n + lx + i, t, 0, INF);
else solver.adde(n + lx + i, t, (cnty[i] - mxy[i] + 1) / 2, (cnty[i] + mxy[i]) / 2);
}
solver.adde();
int flow = solver.work();
cout << 1ll * flow * r + 1ll * (n - flow) * b << '\n';
solver.Print(f, lx, ly);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n >> m) run();
return 0;
}
