顺便附上代码
蒟蒻被T飞了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=500010;
struct edge{
int y,nex,c;
}s[M<<1];
struct node{
int x,y,id;
}p[N];
int first[N],len=1,n,m,H,L,r,b,tp,s1,t1,s2,t2,op[N],sum[N][2],mmin[N][2];
int ans[N],head[N],d[N],qs[N],st,ed;
map<int,int> num[2];
bool cmp1(const node&a,const node&b){return a.x<b.x;}
bool cmp2(const node&a,const node&b){return a.y<b.y;}
void ins(int x,int y,int c){
s[++len]=(edge){y,first[x],c};first[x]=len;
s[++len]=(edge){x,first[y],0};first[y]=len;
}
bool bfs(int S,int T){
for(int i=1;i<=t2;i++) first[i]=head[i],d[i]=0;
d[qs[st=ed=1]=S]=1;
while(st<=ed){
int x=qs[st++];
for(int i=first[x];i!=0;i=s[i].nex) if(s[i].c && !d[s[i].y]){
d[s[i].y]=d[x]+1;
qs[++ed]=s[i].y;
}
}
return d[T]!=0;
}
int dfs(int x,int T,int t){
if(x==T) return t;
int tot=0;
for(int i=first[x];i!=0;i=s[i].nex) if(s[i].c && d[s[i].y]==d[x]+1){
int now=dfs(s[i].y,T,min(t-tot,s[i].c));
s[i].c-=now;s[i^1].c+=now;tot+=now;
if(t==tot) break;
}
return tot;
}
int Dinic(int S,int T){
int tot=0;
while(bfs(S,T)){
int dx=dfs(S,T,1e9);
while(dx) tot+=dx,dx=dfs(S,T,1e9);
}
return tot;
}
int main(){
scanf("%d %d",&n,&m);
scanf("%d %d",&r,&b);
if(r>b) swap(r,b),tp^=1;
for(int i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y),p[i].id=i;
sort(p+1,p+1+n,cmp1);
int las=0;
for(int i=1;i<=n;i++) if(p[i].x==las) p[i].x=p[i-1].x;
else las=p[i].x,p[i].x=p[i-1].x+1,num[0][las]=p[i].x;
H=p[n].x;
sort(p+1,p+1+n,cmp2);las=0;
for(int i=1;i<=n;i++) if(p[i].y==las) p[i].y=p[i-1].y;
else las=p[i].y,p[i].y=p[i-1].y+1,num[1][las]=p[i].y;
L=p[n].y;
s1=H+L+1;t1=s1+1;s2=t1+1;t2=s2+1;
for(int i=1;i<=n;i++)
ins(p[i].x,H+p[i].y,1),ans[p[i].id]=len,sum[p[i].x][0]++,sum[p[i].y][1]++;
for(int i=1;i<=H;i++) mmin[i][0]=sum[i][0];
for(int i=1;i<=L;i++) mmin[i][1]=sum[i][1];
int t,l,d;
while(m--){
scanf("%d %d %d",&t,&l,&d);t--;
if(!num[t][l]) continue;
mmin[num[t][l]][t]=min(mmin[num[t][l]][t],d);
}
for(int i=1;i<=H;i++) {
int L=(sum[i][0]-mmin[i][0]+1)/2,R=sum[i][0]-L;
if(L>R) {printf("-1");return 0;}
op[s1]-=L;op[i]+=L;
if(R-L) ins(s1,i,R-L);
}
for(int i=1;i<=L;i++) {
int L=(sum[i][1]-mmin[i][1]+1)/2,R=sum[i][1]-L;
if(L>R) {printf("-1");return 0;}
op[H+i]-=L;op[t1]+=L;
if(R-L) ins(H+i,t1,R-L);
}
int tot=0;
for(int i=1;i<=t1;i++)
if(op[i]>0) ins(s2,i,op[i]),tot+=op[i];
else if(op[i]<0) ins(i,t2,-op[i]);
ins(t1,s1,1e9);
for(int i=1;i<=t2;i++) head[i]=first[i];
if(Dinic(s2,t2)!=tot) printf("-1\n");
else{
tot=s[len].c,s[len].c=s[len^1].c=0;
tot-=Dinic(t1,s1);
printf("%lld\n",1ll*tot*b+1ll*r*(n-tot));
for(int i=1;i<=n;i++)
printf(s[ans[i]].c^tp?"b":"r");
}
}
```
by Deep_Kevin @ 2020-09-17 20:38:14
回复记得@一下蒟蒻,求求
by Deep_Kevin @ 2020-09-17 20:40:05
@[Deep_Kevin](/user/29093) 你dinic不加当前弧的吗？
那样有可能会巨慢无比
这题容量大于1的边只和某几个特定的点相连，所以单位容量dinic的复杂度分析仍然适用
by 142857cs @ 2020-09-17 21:13:48
@[142857cs](/user/35760) 对对,当前弧都写好了漏打了一个$&$.
那在比赛中如何判断"容量大于1的边只和某几个特定的点相连，所以单位容量dinic的复杂度分析仍然适用"呢?
或者可以说说这题是根据"哪些特定的点",来分析时间复杂度?
by Deep_Kevin @ 2020-09-17 21:39:14
没写当前弧的Dinic复杂度就是错的(听说
by Deep_Kevin @ 2020-09-17 21:40:03
@[Deep_Kevin](/user/29093) 具体是哪些特定的点大概无所谓，只要很少就行
dinic的时间复杂度是 O(单次寻找阻塞流的时间复杂度*寻找阻塞流的次数)
其中单次寻找阻塞流的时间复杂度是O(m+增广路长度之和)
增广路长度之和是O(m)的，因为每条增广路经过的容量大于1的边的数量很少
增广次数是O(sqrt(m))的，因为只用增广O(sqrt(m))次之后，就会有sqrt(m)层之间只有容量为1的边，这样至少有一层满足只有O(sqrt(m))条边，这样残量网络的最大流是O(sqrt(m))的，显然只会增广O(sqrt(m))次
(话说我写这题的时候有没有分析时间复杂度来着？
by 142857cs @ 2020-09-17 22:03:08
@[142857cs](/user/35760) 感谢感谢,顿然醒悟
by Deep_Kevin @ 2020-09-17 22:06:12
非常的amazing啊
by Deep_Kevin @ 2020-09-17 22:10:40