CF2147H

xujindong_ · 2025-09-23 22:13:11 · 题解

问题看上去很不可做。根据一些经验，对这种问题，我们可以猜测一个下界。直接注意到，答案不超过 2。

删去偶数边，我们总可以做到将图黑白染色，使每个点与偶数个同色点相邻，此时最小割/最大流为偶数。可以这么构造：取出一个奇数点删掉，对与这个点相邻的每一对点 (u,v)(u\ne v) 之间加一条边，递归构造子问题。不妨设这个点有偶数个白色邻居，奇数个黑色邻居。则子问题构造出来，白色邻居实际上和奇数个白色点相邻，将这个点染成白色即可。

先判掉答案为 1，用等价流树跑两两最小割。实现时，构造 2 可以直接高斯消元。

#include<bits/stdc++.h>
using namespace std;
int t,n,m,head[55],cur[55],dis[55],cnt=1,p[55],t1[55],t2[55];
struct edge{
  int v,nxt;
  long long w;
}e[1000005];
void add(int u,int v,long long w){
  e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
}
long long dfs(int pos,long long r,int t,edge e[]){
  if(pos==t)return r;
  long long ans=0;
  for(int i=cur[pos];i&&r;i=e[i].nxt){
    cur[pos]=i;
    if(e[i].w&&dis[e[i].v]==dis[pos]+1){
      long long k=dfs(e[i].v,min(r,e[i].w),t,e);
      ans+=k,r-=k,e[i].w-=k,e[i^1].w+=k;
    }
  }
  if(!ans)dis[pos]=-1;
  return ans;
}
long long dinic(int s,int t,int n,edge e[],int head[],long long ans=0){
  while(1){
    queue<int>q;
    for(int i=1;i<=n;i++)dis[i]=-1,cur[i]=head[i];
    dis[s]=0,q.push(s);
    while(!q.empty()){
      int now=q.front();
      q.pop();
      for(int i=head[now];i;i=e[i].nxt){
        if(!e[i].w||dis[e[i].v]!=-1)continue;
        dis[e[i].v]=dis[now]+1,q.push(e[i].v);
      }
    }
    if(dis[t]==-1)return ans;
    ans+=dfs(s,0x3f3f3f3f3f3f3f3f,t,e);
  }
}
int build(int l,int r,edge e[],int head[]){
  if(l>=r)return 0;
  for(int i=2;i<=cnt;i+=2)e[i].w=e[i^1].w=(e[i].w+e[i^1].w)/2;
  int s=p[l],t=p[l+1],w=dinic(s,t,n,e,head),cnt1=0,cnt2=0;
  for(int i=l;i<=r;i++){
    if(dis[p[i]]!=-1)t1[++cnt1]=p[i];
    else t2[++cnt2]=p[i];
  }
  for(int i=1;i<=cnt1;i++)p[l+i-1]=t1[i];
  for(int i=1;i<=cnt2;i++)p[l+i+cnt1-1]=t2[i];
  return __gcd(w,__gcd(build(l,l+cnt1-1,e,head),build(l+cnt1,r,e,head)));
}
int main(){
  cin>>t;
  while(t--){
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,add(u,v,w),add(v,u,w);
    for(int i=1;i<=n;i++)p[i]=i;
    if(build(1,n,e,head)!=1){
      cout<<1<<'\n'<<n<<'\n';
      for(int i=1;i<=n;i++)cout<<i<<(i==n?'\n':' ');
    }
    else{
      bitset<55>f[55];
      for(int i=2;i<=cnt;i+=2)e[i].w=e[i^1].w=(e[i].w+e[i^1].w)/2;
      for(int i=2;i<=cnt;i++)if(e[i].w&1)f[e[i].v].flip(e[i].v),f[e[i].v].flip(e[i^1].v),f[e[i].v].flip(n+1);
      for(int i=1;i<=n;i++){
        int pos=i;
        while(pos<=n&&!f[pos][i])pos++;
        if(pos>n)continue;
        swap(f[i],f[pos]);
        for(int j=1;j<=n;j++)if(i!=j&&f[j][i])f[j]^=f[i];
      }
      int cnt1=0,cnt2=0;
      for(int i=1;i<=n;i++){
        if(f[i][n+1])t1[++cnt1]=i;
        else t2[++cnt2]=i;
      }
      cout<<2<<'\n'<<cnt1<<'\n';
      for(int i=1;i<=cnt1;i++)cout<<t1[i]<<(i==cnt1?'\n':' ');
      cout<<cnt2<<'\n';
      for(int i=1;i<=cnt2;i++)cout<<t2[i]<<(i==cnt2?'\n':' ');
    }
    for(int i=1;i<=n;i++)head[i]=0;
    cnt=1;
  }
  return 0;
}