https://www.luogu.com.cn/problem/CF704D
假设
r
<
c
r<c
r<c
首先肯定是建成二分图,通关简单分析可以知道每个点可以取的范围是
[ x − d + 1 2 , x + d 2 ] [\frac{x-d+1}{2},\frac{x+d}{2}] [2x−d+1,2x+d]都是下取整
所以跑个上下界有源汇最大流即可
code:
#include<bits/stdc++.h>
#define N 400050
using namespace std;
struct edge {
int v, c, nxt;
} e[N << 1];
int p[N], eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v, int c) {
e[eid].v = v;
e[eid].c = c;
e[eid].nxt = p[u];
p[u] = eid ++;
}
void add(int u, int v, int c) { //printf(" %d %d %d\n", u, v, c);
insert(u, v, c), insert(v, u, 0);
}
int d[N], S, T, SS, TT;
queue<int> q;
int bfs() {
for(int i = 0; i <= T; i ++) d[i] = -1;
d[S] = 0; q.push(S);
while(q.size()) {
int u = q.front(); q.pop();
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v;
if(d[v] == -1 && e[i].c) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
//for(int i = 1; i <= T; i ++ ) printf("%d ", d[i]); printf("\n");
return d[T] != -1;
}
int dfs(int u, int flow) {
if(u == T) return flow;
int ret = 0;
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v, c = e[i].c;
if(d[v] == d[u] + 1 && c) {
int tmp = dfs(v, min(c, flow));
e[i].c -= tmp, e[i ^ 1].c += tmp;
ret += tmp, flow -= tmp;
if(!flow) break;
}
}
if(!ret) d[u] = -1;
return ret;
}
const int inf = 1e9;
int Dinic() {
int ret = 0;
for(; bfs() ;) ret += dfs(S, inf);
return ret;
}
int sum[N], totflow;
void addl(int u, int v, int l, int r) {// printf("%d ---> %d %d %d\n", u, v, l, r);
if(l < r) add(u, v, r - l);
sum[u] -= l, sum[v] += l;
}
void build() {
for(int i = 1; i <= TT; i ++) {
if(sum[i] > 0) totflow += sum[i], add(S, i, sum[i]);
if(sum[i] < 0) add(i, T, - sum[i]);
}
add(TT, SS, inf);
}
map<int, int> mpx, mpy;
int n, m, r, b, tot, mi[N], id[N], gs[N], ha[N];
int main() {
//freopen("a.out","w",stdout);
init();
scanf("%d%d%d%d", &n, &m, &r, &b);
int tg = 0;
if(r > b) swap(r, b), tg = 1;
for(int i = 1; i <= n; i ++) {
int x, y;
scanf("%d%d", &x, &y);
if(!mpx[x]) mpx[x] = ++ tot;
if(!mpy[y]) mpy[y] = ++ tot, id[tot] = 1;
gs[mpx[x]] ++, gs[mpy[y]] ++;
add(mpx[x], mpy[y], 1);
ha[i] = eid - 1;
}
for(int i = 1; i <= tot; i ++) mi[i] = inf;
while(m --) {
int o, x, y;
scanf("%d%d%d", &o, &x, &y);
if(o == 1) {
//printf("** %d %d %d\n", x, mpx[x], y);
x = mpx[x];
if(!x) continue;
mi[x] = min(mi[x], y);
} else {
x = mpy[x];
if(!x) continue;
mi[x] = min(mi[x], y);
}
}
//printf("*** %d %d %d\n", tot, mpx[9], mi[5]);
SS = tot + 1, TT = SS + 1, S = TT + 1, T = S + 1;
for(int i = 1; i <= tot; i ++) {
int d = min(mi[i], gs[i]);
int l = (gs[i] - d + 1) / 2, r = (gs[i] + d) / 2;
if(l > r) {printf("-1"); return 0; }
// printf("%d %d %d %d\n", i, mi[i], l, r);
if(!id[i]) addl(SS, i, l, r);
else addl(i, TT, l, r);
}
build();
//printf("%d\n", Dinic());
if(Dinic() != totflow) {printf("-1"); return 0;}
S = SS, T = TT;
long long t = Dinic();
printf("%lld\n", t * r + (n - t) * b);
for(int i = 1; i <= n; i ++) {
if(e[ha[i]].c ^ tg) printf("r");
else printf("b");
}
return 0;
}