自动搬运

查看原文

来自洛谷，原作者为

	yingkeqian9217 千淘万漉虽辛苦，吹尽黄沙始到金​

搬运于2025-08-24 23:14:26，当前版本为作者最后更新于2025-04-23 19:54:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到每个位置是独立的，考虑覆盖它的所有操作，设第 $i$ 个操作执行了 $a_i$ 次，每个限制形如 $a_i+a_j=k$（可以通过建虚点补全限制）。

考虑建图，对于每个限制连接无向边 $i,j$ 边权为 $k$，显然每个连通块独立，而且每个连通块只要确定了其中一个数其他数就唯一确定，直接枚举其中一个，取最小和即可。

时间复杂度 $O(l+b)$。

#include<bits/stdc++.h>
#define maxn 1050005
#define fi first
#define se second
using namespace std;
int n,m,ans,sum,vis[maxn],a[maxn];
char c[maxn];
vector<int>t[maxn],vec;
vector<pair<int,int> >e[maxn];
void dfs1(int x){
	vec.push_back(x);vis[x]=1;
	for(auto i:e[x]) if(!vis[i.fi]) dfs1(i.fi);
}
int dfs2(int x){
	sum+=a[x];
	for(auto i:e[x]){
		int v=i.fi,w=i.se;
		if(a[v]!=-1&&(a[v]+a[x])%3!=w) return 0;
		if(a[v]!=-1) continue;
		a[v]=(w+3-a[x])%3;
		if(!dfs2(v)) return 0;
	}
	return 1;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>c;
	for(int i=1,len,x;i<=m;i++){
		cin>>len;
		while(len--){
			cin>>x;
			t[x].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		if(t[i].empty()&&c[i-1]!='R') return puts("impossible"),0;
		if(t[i].empty()) continue;
		int cur=(c[i-1]=='R'?0:(c[i-1]=='B'?1:2));
		if(t[i].size()==1) t[i].push_back(0);
		e[t[i][0]].emplace_back(t[i][1],cur);
		e[t[i][1]].emplace_back(t[i][0],cur);
	}
	for(int i=0;i<=m;i++){
		if(ans>2*m) break;
		if(vis[i]) continue;
		vec.clear(),dfs1(i);
		for(int i:vec) a[i]=-1;
		a[i]=sum=0;
		int minn=3*m;
		for(int j=0;j<3;j++){
			for(int i:vec) a[i]=-1;
			a[i]=j,sum=(dfs2(i)?sum:3*m);
			minn=min(minn,sum),sum=0;
			if(!i) break;
		}
		ans+=minn;
	}
	if(ans>2*m) puts("impossible");
	else cout<<ans<<'\n';
	return 0;
}