给定一个二部图,每条边可以为红色/蓝色/无色,且一条边为红色需要付出\(r\)的代价,为蓝色需要\(b\)的代价
每个点可以为红色/蓝色/无色
1.如果该点为红色,则其所连的边中红色边边数 严格大于 蓝色边边数
2.如果该点为蓝色,则其所连的边中蓝色边边数 严格大于 红色边边数
求最小化代价满足上述限制
二分图果然和网络流密不可分
考虑从奇怪的题目中归纳一个费用流模型
用一个点的流量表示红色边-蓝色边的数量,将问题描述为
1.一条边如果选为红色,那么这个点从\(S\)强制得到\(1\)的流量
2.一个边如果选蓝色,那么这个点强制向\(T\)流\(1\)的流量
3.如果一个点时红色,那么它最终应该仍然有流量多
那么强制这个点必须还能向\(T\)流\(1\)的流量,剩余随意
4.如果一个点时蓝色,那么它最终应该仍然不存
那么强制这个点必须从\(S\)得到\(1\)的流量,剩余随意
然而这个模型无法解决一条边对于其两端点的决策
常见的处理二分图思路:考虑将右半边图红蓝反着建立
此时令一条边对应的中继节点从\(S\)得到\(2\)的流量
这个节点向左边的点流0,表示这条边选择蓝色
这个节点向左边的点流1,表示这条边选择白色
这个节点向左边的点流2,表示这条边选择红色
同时将代价加入即可
这样给每个点额外增加了一个基准偏移的流量,需要简单处理一下
用代价为\(-\infty\)的边表示这条边强制选择
注意最终求出的是最小费用,而不是最大流
const int N=2e5+10,INF=1e9+10; int n1,n2,S,T,V,m,r,b; struct Edge{ int to,nxt,w,c; } e[N]; int head[N],ecnt=1; void AddEdge(int u,int v,int w,int c){ e[++ecnt]=(Edge){v,head[u],w,c}; head[u]=ecnt; } void Link(int u,int v,int w,int c){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); } ll ans,dis[N]; char s[N]; int inq[N],pre[N],w[N]; int main(){ n1=rd(),n2=rd(),m=rd(),r=rd(),b=rd(),S=n1+n2+1,T=S+1,V=T; scanf("%s",s+1); rep(i,1,n1) { if(s[i]=='R') Link(i,T,1,-INF),ans+=INF,Link(i,T,INF,0); if(s[i]=='B') Link(S,i,1,-INF),ans+=INF,Link(S,i,INF,0); if(s[i]=='U') Link(S,i,INF,0),Link(i,T,INF,0); } scanf("%s",s+1); rep(i,1,n2) { if(s[i]=='B') Link(i+n1,T,1,-INF),ans+=INF,Link(i+n1,T,INF,0); if(s[i]=='R') Link(S,i+n1,1,-INF),ans+=INF,Link(S,i+n1,INF,0); if(s[i]=='U') Link(S,i+n1,INF,0),Link(i+n1,T,INF,0); } rep(i,1,m) { int u=rd(),v=rd()+n1; Link(S,++V,2,-INF),ans+=2*INF; Link(V,u,1,0),Link(V,v,1,0); Link(V,u,1,r),Link(V,v,1,b); Link(u,T,1,-INF),ans+=INF; Link(v,T,1,-INF),ans+=INF; } while(1) { static queue <int> que; rep(i,1,V) dis[i]=1e18; dis[S]=0,que.push(S),w[S]=INF; while(!que.empty()) { int u=que.front(); que.pop(); inq[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to,c=e[i].c; if(!e[i].w || dis[v]<=dis[u]+c) continue; dis[v]=dis[u]+c,w[v]=min(e[i].w,w[u]),pre[v]=i; if(!inq[v]) que.push(v),inq[v]=1; } } if(dis[T]>0) break; int c=w[T]; ans+=dis[T]*c; for(int u=T;u!=S;u=e[pre[u]^1].to) { //cout<<u<<endl; e[pre[u]].w-=c,e[pre[u]^1].w+=c; } } if(ans>INF) puts("-1"); else { printf("%lld\n",ans); rep(u,T+1,T+m) { int c=0; for(int i=head[u];i;i=e[i].nxt) if(e[i].to<=n1) c+=e[i^1].w; putchar("BUR"[c]); } } }