[GCJ 2022 #3] Mascot Maze 题解

FFTotoro · 2025-07-04 14:51:36 · 题解

感觉是挺好的 trick。

这题是图的点染色问题的特殊情况，注意到原图上每个点的出度都最多为 6，所以建出“矛盾图”（即对于不能颜色相同的点连边）之后，最小度数的点度数不超过 12。

证明：其中 6 个为原来的“出度”，由于有向图出度和不超过 6n 故入度也不超过 6n，所以度数最小的点入度和必然不超过 6，即平均值，所以度数最多为 12。

每次删掉一个度数 \le 12 的点和与它相连的边之后，图仍然满足这个性质。最后倒着推回来，由于颜色有 13 种所以填完 12 条出边以后至少剩下一种，故方案一定合法。

使用队列进行 BFS 模拟删掉度数 \le 12 的点，前面的去重环节需要带个 \log，总时间复杂度 O(TN\log N)。

放代码：

#include<bits/stdc++.h>
using namespace std;
const string S="ACDEHIJKMORST";
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int tt; cin>>tt;
  for(int t=1;t<=tt;t++){
    int n; cin>>n;
    vector<int> l(n),r(n);
    for(auto &i:l)cin>>i,i--;
    for(auto &i:r)cin>>i,i--;
    vector<vector<int> > g(n);
    bool f=true;
    for(int u=0;u<n&&f;u++)
      for(int i:{l[u],r[u]}){
        g[u].emplace_back(i);
        g[i].emplace_back(u);
        for(int j:{l[i],r[i]}){
          if(u==j){f=false; break;}
          g[u].emplace_back(j);
          g[j].emplace_back(u);
        }
      } // 建出“矛盾图”
    cout<<"Case #"<<t<<": ";
    if(!f){cout<<"IMPOSSIBLE\n"; continue;}
    vector<int> d(n),v,c(n,-1);
    vector<bool> b(n);
    queue<int> q;
    for(int u=0;u<n;u++){
      sort(g[u].begin(),g[u].end());
      g[u].erase(unique(g[u].begin(),g[u].end()),g[u].end());
      if((d[u]=g[u].size())<=12)b[u]=true,q.emplace(u);
    } // 对边去重，并加入初始时度数不大于 12 的点
    while(!q.empty()){
      int u=q.front(); q.pop();
      v.emplace_back(u);
      for(int i:g[u])
        if(--d[i]<=12&&!b[i])b[i]=true,q.emplace(i);
    } // 执行一个类似拓扑排序的过程
    reverse(v.begin(),v.end());
    for(int u:v){
      vector<bool> b(13);
      for(int i:g[u])
        if(~c[i])b[c[i]]=true;
      for(int i=0;i<13;i++)
        if(!b[i]){c[u]=i; break;}
    } // 倒推回来染色
    for(int i:c)cout<<S[i];
    cout<<'\n';
  }
  return 0;
}