正题
首先我们假设全部选权值较小的颜色,将行列离散化,转化为二分图,对于一行或一列的限制来说,更改颜色数量的区间是一个范围,以此作为上下界与源汇连边,中间存在点(i,j)那么就从i向j连边,容量为1,最后看看可行的最小流是多少,就知道至少要改多少个成权值较大的颜色,才能满足方案.
输出方案我们就把中间边的编号记下来,看看有没有流量即可,有流量说明改了.
当前弧优化漏打一个&,T了半小时.
#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 gmin(int&x,int d){x=min(x,d);}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;gmin(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");}
}