CF上的题，就不放链接了，打开太慢，直接上题面吧：
平面上有n个点, 第 i 个点的坐标为 ($X_i ,Y_i$), 你需要把每个点
染成红色或者蓝色, 染成红色的花费为 r , 染成蓝色的花费为 b .
有m个限制条件, 有两种类型, 第一种类型为$x = l_i$ 上的红点
与蓝点个数差的绝对值不超过 $d_i$, 第二种类型为$y= l_i$ 上的红
点与蓝点个数差的绝对值不超过 $d_i$.
题解：
表示这题真的写到失去理想，因为是第一次写带上下限的网络最大流，一开始就把建图和统计代价理解错了好多次。。。
首先我们可以观察到r, b是固定的，假设r比b小，那么我们就肯定要让涂红色尽可能多，这样才会更优。
因此我们就不用考虑这个代价了，只需要找到一个合法的方案且使得涂红色的尽可能多即可。
由于一个点要么涂红，要么涂蓝，因此我们并不需要求出涂蓝的个数，因为只要知道涂红的个数，涂蓝的个数自然就知道了。
因此现在问题就被简化为了：
二维平面上有n个点，有m个限制，要求被选中的点尽可能多。
对于任何一个限制，假设这条线上有num个点，那么我们可以得出被选中点的上限和下限：$[\frac{num - d}{2}, \frac{num + d}{2}]$。
而对于任何一个点是否被选，也可以看做有一个上限和下限$[0,1]$,即要么不选，要么选一个。
那么我们将行和列分别用点表示，如果有点(x, y),那么从第x行向第y列连一条[0, 1]的边.
对于x的限制，从s 到第x行连[下限，上限]的边。
然后跑带上下限的最大流就可以知道最多选多少点了。
如何不知道带上下限最大流怎么写请看：算法学习——带上下界网络流
这题的建图因为还要离散化，所以写起来十分恶心。。。。
代码比较冗长，建议只看思路。
（注意在cf上提交的时候只能用I64d,不能用lld)
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 500000
#define ac 2000000
#define inf 2139062143
#define INF 2139062143
#define LL long long int n, m, g, s, t, ss, ff, ww, tt, top1, top2, got, must;
int cnt1, cnt2, x, head, tail, addflow;
int Head[AC], Next[ac], belong[ac], date[ac], haveflow[ac], tot = ;
int lim1_x[AC], lim2_x[AC], lim1_y[AC], lim2_y[AC], q[AC];
int num1[AC], num2[AC], q1[AC], q2[AC], c[AC], have[AC], good[AC], last[AC];
bool z[AC], flag, vis1[AC], vis2[AC];
LL d[AC], ans, red, blue; struct node{
int x, y;
}p[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} inline void add(int f, int w, int up, int down)
{
belong[tot] = f, date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, haveflow[tot] = up - down, d[f] -= down;
date[++tot] = f, Next[tot] = Head[w], Head[w] = tot, haveflow[tot] = , d[w] += down;
if(w == tt) must += up - down;
// printf("%d ---> %d : %d\n", f, w, up - down);
} inline void upmin(int &a, int b)
{
if(b < a) a = b;
} inline void upmax(int &a, int b)
{
if(b > a) a = b;
} inline int half1(int x)
{
int l = , r = cnt1, mid;
while(l < r)
{
mid = (l + r) >> ;
if(q1[mid] > x) r = mid - ;
else if(q1[mid] < x) l = mid + ;
else return mid;
}
if(q1[l] != x) return ;
else return l;
} inline int half2(int x)
{
int l = , r = cnt2, mid;
while(l < r)
{
mid = (l + r) >> ;
if(q2[mid] > x) r = mid - ;
else if(q2[mid] < x) l = mid + ;
else return mid;
}
if(q2[l] != x) return ;
else return l;
} void link(int x)
{
if(d[x] > ) add(ss, x, d[x], );
else if(d[x] < ) add(x, tt, -d[x], );
} #define c c_
#define d d_ void get_lim()
{
int opt, a, b;
for(R i = ; i <= m; i ++)
{
opt = read(), a = read(), b = read();
if(!a) continue;
if(opt == )//x 的限制
{
a = half1(a);
int c = (num1[a] + b) / , d = (num1[a] - b + ) / ;
if(d > c) {puts("-1"); exit();}//,...这里需要判断
upmin(lim1_x[a], c), upmax(lim1_y[a], d), vis1[a] = true;
}
else
{
a = half2(a);
int c = (num2[a] + b) / , d = (num2[a] - b + ) / ;
if(d > c) {puts("-1"); exit();}
upmin(lim2_x[a], c), upmax(lim2_y[a], d), vis2[a] = true;
}
}
} void pre()
{
n = read(), m = read(), red = read(), blue = read();
s = n + m + , t = s + , ss = t + , tt = ss + ;
memset(lim1_x, , sizeof(lim1_x));
memset(lim2_x, , sizeof(lim2_x));
for(R i = ; i <= n; i ++)
q1[++top1] = p[i].x = read(), q2[++top2] = p[i].y = read();
sort(q1 + , q1 + top1 + );
sort(q2 + , q2 + top2 + );
for(R i = ; i <= top1; i ++)
if(q1[i] != q1[i + ]) q1[++cnt1] = q1[i];
for(R i = ; i <= top2; i ++)
if(q2[i] != q2[i + ]) q2[++cnt2] = q2[i];
g = cnt1, ff = tot + ;
for(R i = ; i <= n; i ++)
{
p[i].x = half1(p[i].x), p[i].y = half2(p[i].y);
add(p[i].x, p[i].y + g, , );
++num1[p[i].x], ++num2[p[i].y];
}
ww = tot;
get_lim();
for(R i = ; i <= cnt1; i ++)
if(vis1[i]) add(s, i, lim1_x[i], lim1_y[i]);
for(R i = ; i <= cnt2; i ++)
if(vis2[i]) add(i + g, t, lim2_x[i], lim2_y[i]);
for(R i = ; i <= n; i ++)
{
if(!vis1[p[i].x])
vis1[p[i].x] = true, add(s, p[i].x, inf, );
if(!vis2[p[i].y])
vis2[p[i].y] = true, add(p[i].y + g, t, inf, );
}
add(t, s, inf, );
link(s), link(t);
for(R i = ; i < s; i ++) link(i);
}
#undef c
#undef d void bfs()
{
int x, now, k = flag ? t : tt;
if(flag) memset(have, , sizeof(have));
if(flag) memset(c, , sizeof(c));
head = tail = ;
q[++tail] = k, c[k] = , have[] = ;
while(head < tail)
{
x = q[++head];
for(R i = Head[x]; i; i = Next[i])
{
now = date[i];
if(flag && (now == ss || now == tt)) continue;
if(!c[now]/* && haveflow[i ^ 1]*/)
{
c[now] = c[x] + ;
q[++tail] = now;
++ have[c[now]];
}
}
}
memcpy(good, Head, sizeof(Head));
} void aru()
{
int k = flag ? s : ss;
while(x != k)
{
//if(flag) printf("%d ---> %d\n", x, date[last[x] ^ 1]);
haveflow[last[x]] -= addflow;
haveflow[last[x] ^ ] += addflow;
x = date[last[x] ^ ];
}
//printf("\n\n");
if(flag) ans += addflow;
else got += addflow;
} void isap()
{
int now; bool done;int k = flag ? t : tt, kk = flag ? s : ss;
addflow = inf, x = kk;
while(c[kk] != k + )
{
if(x == k) aru(), addflow = inf;
done = false;
for(R i = good[x]; i; i = Next[i])
{
now = date[i];
if(flag && (now == ss || now == tt)) continue;
if(c[now] == c[x] - && haveflow[i])
{
upmin(addflow, haveflow[i]);
good[x] = i, last[now] = i;
x = now, done = true;
break;
}
}
if(!done)
{
int go = k + ;
for(R i = Head[x]; i; i = Next[i])
{
now = date[i];
if(flag && (now == ss || now == tt)) continue;
if(haveflow[i] && c[now]) upmin(go, c[now]);
}
if(!(-- have[c[x]])) break;
++have[c[x] = go + ];
good[x] = Head[x];
if(x != kk) x = date[last[x] ^ ];
}
}
} void write(bool k)
{
if(k)
{
if(red < blue) putchar('r');
else putchar('b');
}
else
{
if(red > blue) putchar('r');
else putchar('b');
}
} void find()
{
for(R i = ff; i <= ww; i += ) write(haveflow[i ^ ]);
printf("\n");
} void work()
{
LL k = min(red, blue), kk = max(red, blue);
flag = true;
if(got != must) {puts("-1"); return ;}
bfs();
isap();
ans = k * ans + kk * (n - ans);
printf("%lld\n", ans);
find();
} int main()
{
freopen("in.in", "r", stdin);
pre();
bfs();
isap();
work();
fclose(stdin);
return ;
}