「CF1288F」Red-Blue Graph

发表于 分类于

题目链接：https://codeforces.com/contest/1288/problem/F。

网络流建模太难了，wsl。

考虑网络流建模，把二分图上的点全建出来，边弄成容量为$1$的双向边，那么如果这条边是从左流到右的，我们看作是红色的，从右到左看作蓝色，没有流量就是无色，并且把红蓝的费用标上（因为要求最小费用，所以没可能两条边都有流量）。

那么对于左边的点，如果它是红色的，就说明一定要多流出去一条边，那么我们就从源点向他连一条边，容量无穷费用为$0$，并且流量下界是$1$；如果是蓝色的，就向汇点连同样的边。

右边同理，然后跑最小费用可行流就是答案。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define data asd09123jdf02i3h
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e5;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,m,k,a,b;
char s[maxn],t[maxn];
 
int head[maxn],tot=1,S,T,dis[maxn],vis[maxn],id[maxn],pre[maxn],min_cost,max_flow,ss,tt,ans,d[maxn];
struct edge{int to,nxt,w,c;}e[maxn<<1];
 
void add(int u,int v,int w,int c) {e[++tot]=(edge){v,head[u],w,c},head[u]=tot;}
void ins(int u,int v,int w,int c) {add(u,v,w,c),add(v,u,0,-c);}
 
void ins1(int u,int v,int w,int c) {ans+=c,d[u]--,d[v]++,ins(u,v,w,c);}
 
int spfa() {
    memset(dis,63,4*(tt+3));
    queue<int > q;q.push(S),dis[S]=0;
    while(!q.empty()) {
        int x=q.front();q.pop(),vis[x]=0;
        for(int v,i=head[x];i;i=e[i].nxt)
            if(e[i].w&&dis[v=e[i].to]>dis[x]+e[i].c) {
                pre[v]=x,id[v]=i,dis[v]=dis[x]+e[i].c;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
    }
    if(dis[T]>1e9) return 0;
    int x=T;max_flow++;
    while(x) {
        e[id[x]].w--,e[id[x]^1].w++;
        x=pre[x];
    }
    min_cost+=dis[T];
    return 1;
}
 
int main() {
    read(n),read(m),read(k),read(a),read(b);
    scanf("%s%s",s+1,t+1);S=n+m+1,T=n+m+2,ss=T+1,tt=ss+1;
    for(int i=1,x,y;i<=k;i++) read(x),read(y),ins(x,y+n,1,a),ins(y+n,x,1,b);
    for(int i=1;i<=n;i++)
        if(s[i]=='R') ins1(ss,i,k,0);
        else if(s[i]=='B') ins1(i,tt,k,0);
        else ins(ss,i,k,0),ins(i,tt,k,0);
    for(int i=1;i<=m;i++)
        if(t[i]=='B') ins1(ss,i+n,k,0);
        else if(t[i]=='R') ins1(i+n,tt,k,0);
        else ins(ss,i+n,k,0),ins(i+n,tt,k,0);
    int p=0;ins(tt,ss,inf,0);
    for(int i=1;i<=n+m+4;i++)
        if(d[i]<0) ins(i,T,-d[i],0),p-=d[i];
        else if(d[i]>0) ins(S,i,+d[i],0);
    while(spfa()) ;
    if(max_flow!=p) return puts("-1"),0;
    write(ans+min_cost);
    for(int i=0;i<k;i++)
        if(!e[i*4+2].w) putchar('R');
        else if(!e[i*4+4].w) putchar('B');
        else putchar('U');
    puts("");
    return 0;
}