CF1288F - Red-Blue Graph

题目大意

给定一个二部图，每条边可以为红色/蓝色/无色，且一条边为红色需要付出$r$的代价，为蓝色需要$b$的代价

每个点可以为红色/蓝色/无色

1.如果该点为红色，则其所连的边中红色边边数 严格大于 蓝色边边数

2.如果该点为蓝色，则其所连的边中蓝色边边数 严格大于 红色边边数

求最小化代价满足上述限制


分析

二分图果然和网络流密不可分

考虑从奇怪的题目中归纳一个费用流模型

用一个点的流量表示红色边-蓝色边的数量，将问题描述为

1.一条边如果为红色，那么所关联的点从$S$强制得到$1$的流量

2.一个边如果选蓝色，那么所关联的点强制向$T$流$1$的流量

3.如果一个点为红色，那么它最终应该仍然有流量多

那么强制这个点必须还能向$T$流$1$的流量，剩余随意

4.如果一个点为蓝色，那么它最终应该仍然流量不足

那么强制这个点必须从$S$得到$1$的流量，剩余随意

然而这个模型无法解决一条边对于其两端点的决策


常见的处理二分图思路：考虑将右半边图红蓝反着建立

此时令一条边对应的中继节点从$S$得到$2$的流量

这个节点向左边的点流0，表示这条边选择蓝色

这个节点向左边的点流1，表示这条边选择白色

这个节点向左边的点流2，表示这条边选择红色

同时将代价加入即可

这样给每个点额外增加了一个基准偏移的流量，需要简单处理一下

用代价为$-\infty$的边表示这条边强制选择

注意最终求出的是最小费用，而不是最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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]);
		}
	}
}