[GCJ Farewell Round #3] The Decades of Coding Competitions 题解

FFTotoro · 2025-07-04 14:35:01 · 题解

考虑一个 s\to t 怎样能走奇数种颜色，首先考虑整个连通块里面的颜色种类数，如果为奇数整个遍历一遍即可取到——故必然有解，如果为偶数判断是否存在一个连通块内存在的颜色使得删掉这个颜色的边 s,t 仍然连通（对于每个颜色开一个并查集维护），有解当且仅当存在。

证明：考虑一个不必经过的颜色 c，如果不经过它可以遍历连通块内的其他所有颜色，那么遍历其他所有颜色即可；否则必然存在一个颜色 c' 被它“隔开”了，此时 c\gets c'，继续返回去判断上面的条件……这个过程一定会结束，所以一定存在一组解。

视 N,M,Q 同阶，令颜色数为 C，时间复杂度 O(CN\alpha(N))。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
const int C=100;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(int n=2e5){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  }; // 并查集模板
}
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,m,q,c=0; cin>>n>>m>>q;
    vector<tpi> e(m);
    vector<vector<pii> > g(n);
    for(auto &[u,v,c]:e){
      cin>>u>>v>>c,u--,v--,c--;
      g[u].emplace_back(v,c);
      g[v].emplace_back(u,c);
    }
    vector d(C,IAOI_lib::dsu<int>(n));
    // 每个颜色开一个并查集维护
    for(int i=0;i<C;i++)
      for(auto [u,v,c]:e)
        if(c!=i)d[i].merge(u,v);
    vector<int> p(n,-1);
    vector h(n,vector<bool>(C));
    for(int s=0;s<n;s++)
      if(p[s]<0){
        queue<int> q; q.emplace(p[s]=s);
        while(!q.empty()){
          int u=q.front(); q.pop();
          for(auto [i,w]:g[u]){
            if(p[i]<0)q.emplace(i);
            h[p[i]=s][w]=true;
          }
        }
      } // 搜连通块，顺带得出其中有哪几种颜色
    while(q--){
      int u,v,w=0; cin>>u>>v,u--,v--;
      if(p[u]!=p[v])continue;
      for(int i=0;i<C;i++)
        w^=h[p[u]][i];
      if(w){c++; continue;}
      for(int i=0;i<C;i++)
        if(h[p[u]][i]&&d[i].same(u,v)){c++; break;}
      // 判断是否有不必经过的颜色存在
    }
    cout<<"Case #"<<t<<": "<<c<<'\n';
  }
  return 0;
}