题解：P12301 [ICPC 2022/2023 WF] 变成红灯

· · 题解

注意到每个位置是独立的，考虑覆盖它的所有操作，设第 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;
}