有一张二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，$m$ 条边。每个点可能有一种颜色 `R` 或者 `B`，也可能没有，也就是 `U`。现在要给一些边染色，把边染成 `R` 要花费 $r$ 的代价，把边染成 `B` 要花费 $b$ 的代价，要求对于每个颜色为 `R` 的点，与之相邻的边中 `R` 的边**严格多于** `B` 的边；对于每个颜色为 `B` 的点，与之相邻的边中 `B` 的边**严格多于** `R` 的边。求花费最小的方案，输出任意一种，无解输出 $-1$。 数据范围：$1 \le n_1,n_2,m,r,b\le 200$。

题面

CF1288F Red-Blue Graph

有一张二分图，左边有 \(n_1\) 个点，右边有 \(n_2\) 个点，\(m\) 条边。每个点可能有一种颜色 R 或者 B，也可能没有，也就是 U。现在要给一些边染色，把边染成 R 要花费 \(r\) 的代价，把边染成 B 要花费 \(b\) 的代价，要求对于每个颜色为 R 的点，与之相邻的边中 R 的边严格多于 B 的边；对于每个颜色为 B 的点，与之相邻的边中 B 的边严格多于 R 的边。求花费最小的方案，输出任意一种，无解输出 \(-1\)。

数据范围：\(1 \le n_1,n_2,m,r,b\le 200\)。

---

蒟蒻语

蒟蒻昨天打了一场 \(\rm VP\)，然后今天补了一个下午的题。中途的时候，zaky 说要打蒟蒻打过的 \(\rm VP\)，于是怹去打了。等蒟蒻补完题后蒟蒻看到 zaky 站了起来，说：“朕 AK 了”。

这题有一个不需要上下界只需要最小费用最大流的骚操作，蒟蒻觉得挺妙的于是写篇题解。

---

蒟蒻语

先令原图每个右边的节点 \(u\) 编号为 \(u+n_1\)，有色点个数为 \(cnt\)。

首先将一条二分图上的边 \((u,v)\) 转化为网络流上的边：

\((u,v,flow=1,cost=r)\)，如果流了表示选了红色；

\((v,u,flow=1,cost=b)\)，如果流了表示选了蓝色；

都没流表示无色。

对于一个左边的节点 \(u\)，如果颜色为 R，连 \((s,u,flow=1,cost=-\infty),(s,u,flow=\infty,cost=0)\)。

对于一个右边的节点 \(u\)，如果颜色为 R，连 \((u,t,flow=1,cost=-\infty),(u,t,flow=\infty,cost=0)\)。

这样就可以引诱网络流算法先满足红点的限制。

对于一个左边的节点 \(u\)，如果颜色为 B，连 \((u,t,flow=1,cost=-\infty),(u,t,flow=\infty,cost=0)\)。

对于一个右边的节点 \(u\)，如果颜色为 B，连 \((s,u,flow=1,cost=-\infty),(s,u,flow=\infty,cost=0)\)。

这样就可以引诱网络流算法先满足蓝点的限制。

对于一个节点 \(u\)，如果颜色为 U，连 \((s,u,flow=\infty,cost=0),(u,t,flow=\infty,cost=0)\)。

这样可以使它不优先考虑，同时可以选择辅助满足另外两种颜色的条件。

然后跑最小费用最大流。

如果满足了所有条件，那么答案肯定包含 \(cnt\) 个 \(-\infty\)，所以要给跑出来的总 \(cost\) 加上 \(cnt\cdot \infty\)。如果 \(cost\ge \infty\)，那么肯定有条件没有满足，输出 \(-1\)。

这样直接交会 WA#\(19\)，因为有个小问题：虽然这是个最小费用流，但是它毕竟还是个最大流，所以它把所有负权路径跑完后就开始跑正权路径了。

如果可以满足条件，那么跑负权路径就够了，正权路径相当于选了多余的有色边，这是不必要的。

可以发现如果用 \(\rm EK\) 算法，满足条件和跑多余边肯定是分开计算的，而且肯定是先负权再正权，所有可以在分界点上 break，不再跑网络流。

---

代码

#include <bits/stdc++.h>
using namespace std;

//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair((a),(b))
#define x first
#define y second
#define be(a) (a).begin()
#define en(a) (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define R(i,a,b) for(int i=(a),I=(b);i<I;i++)
#define L(i,a,b) for(int i=(b)-1,I=(a)-1;i>I;i--)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Mcmf
const int T=402;
int tn,s,t;
vector<int> e[T],to,fw,co;
int  adde(int u,int v,int w,int c){
//	cout<<u<<" - "<<v<<" ("<<w<<" , "<<c<<")\n";
	e[u].pb(sz(to)),to.pb(v),fw.pb(w),co.pb(+c);
	e[v].pb(sz(to)),to.pb(u),fw.pb(0),co.pb(-c);
	return sz(to)-2;
}
int dep[T],pre[T]; bool vis[T];
bool spfa(){
	fill(vis,vis+tn,false);
	fill(dep,dep+tn,iinf);
	fill(pre,pre+tn,-1);
	queue<int> q; q.push(s),vis[s]=true,dep[s]=0;
	while(sz(q)){
		int u=q.front(); q.pop(),vis[u]=false;
		for(int v:e[u])if(fw[v]&&dep[to[v]]>dep[u]+co[v]){
			dep[to[v]]=dep[u]+co[v],pre[to[v]]=v;
			if(!vis[to[v]]) vis[to[v]]=true,q.push(to[v]);
		}
	}
	return dep[t]<iinf;
}
int flow,cost;
void mcmf(){
	while(spfa()){
		if(dep[t]>=0) break; // 题解的精华
		int f=iinf;
		for(int i=t;i!=s;i=to[1^pre[i]]) f=min(f,fw[pre[i]]);
		for(int i=t;i!=s;i=to[1^pre[i]]) fw[pre[i]]-=f,fw[pre[i]^1]+=f;
		cost+=dep[t]*f,flow+=f;
	}	
}

//Data
const int N=200;
int n1,n2,m,r,b,re[N],be[N],cnt;
string sa,sb;

//Main
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n1>>n2>>m>>r>>b>>sa>>sb;
	tn=(t=(s=n1+n2)+1)+1; 
	R(i,0,m){
		int u,v; cin>>u>>v,--u,--v;
		re[i]=adde(u,v+n1,1,r),be[i]=adde(v+n1,u,1,b);
	}
	int mx=4e6;
	R(i,0,n1){
		if(sa[i]=='R') adde(s,i,1,-mx),cnt++;
		else adde(i,t,mx,0);
		if(sa[i]=='B') adde(i,t,1,-mx),cnt++;
		else adde(s,i,mx,0);
	}
	R(i,0,n2){
		if(sb[i]=='R') adde(i+n1,t,1,-mx),cnt++;
		else adde(s,i+n1,mx,0);
		if(sb[i]=='B') adde(s,i+n1,1,-mx),cnt++;
		else adde(i+n1,t,mx,0);
	}
	mcmf(),cost+=cnt*mx;
	if(cost>=mx) cout<<-1<<'\n',exit(0);
	cout<<cost<<'\n';
	R(i,0,m){
		if(fw[re[i]^1]) cout<<'R';
		else if(fw[be[i]^1]) cout<<'B';
		else cout<<'U';
	}
	cout<<'\n';
	return 0;
}

---

祝大家学习愉快！