CF2147H Maxflow GCD Coloring

· · 题解

2025-10-16 修改了一处笔误。

jiangly 讲的。

题意

给定图 G，将每个点染色为 c 种颜色的一种，使得存在 d\ge 2 满足每种颜色的导出子图上，任意两点间的最大流都为 d 的倍数，最小化 c 并构造方案。

小剧场

jiangly：那这个题其实，就看上去它就很很很……很难，看上去它就很……很复杂。

jiangly：就这种题，我觉得大家不知道就是……能不能有这种……感觉了就是……实际上也是题做多了就是，你感觉这个题要么答案是 1 要么答案是 2 不然它就做不了，对吧有这样一种感觉。

jiangly：就是……就简单来说就是……如果它要分 3 份我就不会做了，所以它一定是分 2 份，嗯懂我意思吗。

题解

考虑 c 的最小值一定是 1 或 2，证明见后续构造。

当 c=1 时，可以直接使用最小割树判断。

当 c=2 时，考虑令 d=2，我们要使所有点对间的最小割/最大流为偶数。

这里有一个结论：去掉所有偶数边后，若每个点的度数均为偶数，则任意两点间的最小割也为偶数。

jiangly 没有讲这个东西为什么对，或许很显然吧。

:::info[一种证明]

考虑满足上述条件时始终存在欧拉回路。

对于一个点对 (s,t)，欧拉回路上一定可以分出若干 s\rightarrow t\rightarrow s 的路径。

对于每一段这样的路径，我们必然需要割掉至少一条边，最小割也包含在内，因此最小割必然割掉偶数条边，由于边的容量全为奇数，所以此时最小割为偶数。

考虑加回偶数边，这些边无论怎么加都不会影响原本的最小割，产生的新的割边也不影响答案的奇偶性，所以最小割仍为偶数。

证毕。

:::

现在我们将所有偶数边去掉，对于剩下的图，我们需要给每个点染色，使得每种颜色的导出子图上，所有点的度数均为偶数。

考虑增量构造，我们每次加入一个点并决定其颜色，为方便下设两种颜色的点集分别为 A,B。

先通过递归，每次删除一个奇数度数的点 u，同时对于所有点对 (v,w) 连边，其中 v,w 都是 u 的邻居，直到最后剩下的点全为偶数度数（显然至多删成一个点就不会再删了），将它们全部加入点集 A。

考虑往回加入点 u，由于点 u 的邻居有奇数个，则必然有一个点集中包含奇数个 u 的邻居，设该集合为 S，另一个为 T。

结论：我们应当把 u 加入 T。

这是因为原本 S,T 都满足其中所有点的度数均为偶数，而在加入 u 之后，我们需要删除所有在这时删除的边。

显然，此时度数会发生变化的点只有 u 和 u 的邻居，对于 u 而言，它显然只能加入 T。

再考察所有 u 的邻居来确定这是对的，分别对两个集合内的邻居来看：

对于 S，其中有奇数个点是 u 的邻居，由于 u 没有加入 S，S 中所有 u 的每个邻居的度数减少了 S 中 u 的邻居数 -1，这无疑是一个偶数。

对于 T，同上分析，所有 u 的邻居的度数减少了一个奇数，其奇偶性发生了改变，然而 u 加入之后每个 u 的邻居多了一条边，度数又变回来了。

所以上述构造方案是合法的，我们始终能够构造出这样的一组解。

:::info[代码]

人傻常数大，写得还丑，看个乐子就好。

然而这里有个细节是在构造时会出现巨量的重边，甚至到 long long 都存不下的地步，但是我们只关注奇偶性，所以可以存成 bool。

/*
CF2147H Maxflow GCD Coloring
https://www.luogu.com.cn/article/ih2b8110。
*/
#include<bits/stdc++.h>
using namespace std;
#define fprintf(...)
constexpr int N=55,M=5555,INF=1e9;
struct edge{int v,w,nex;}e[M];
int fir[N],ent=1;
inline void add(int u,int v,int w)
{
    e[++ent]={v,w,fir[u]};
    fir[u]=ent;
    e[++ent]={u,w,fir[v]};
    fir[v]=ent;
    return;
}
class GomoryHuTree
{
private:
    int s,t;
    edge e[M];
    int fir[N],cur[N];
    void init(int a,int b)
    {
        memcpy(e,::e,sizeof e);
        memcpy(fir,::fir,sizeof fir);
        s=a,t=b;
        return;
    }
    queue<int>q;
    int dis[N];
    bool BFS()
    {
        memset(dis,-1,sizeof dis);
        q.push(s);
        dis[s]=0;
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=fir[u];i;i=e[i].nex)
            {
                int v=e[i].v;
                if(e[i].w&&dis[v]==-1)q.push(v),dis[v]=dis[u]+1;
            }
        }
        return dis[t]!=-1;
    }
    bool vis[N];
    int flow(int u,int max_flow)
    {
        fprintf(stderr,"flow: %d %d\n",u,max_flow);
        if(u==t)return max_flow;
        int all_flow=max_flow;
        vis[u]=true;
        for(int i=cur[u];i&&all_flow;i=e[i].nex)
        {
            cur[u]=i;
            int v=e[i].v,w=e[i].w;
            if(!w||vis[v]||dis[v]!=dis[u]+1)continue;
            int f=flow(v,min(all_flow,w));
            e[i].w-=f,e[i^1].w+=f,all_flow-=f;
        }
        vis[u]=false;
        return max_flow-all_flow;
    }
    int dinic()
    {
        int ret=0;
        while(BFS())memcpy(cur,fir,sizeof cur),ret+=flow(s,INF);
        return ret;
    }
    vector<pair<int,int>>T[N];
    void getV(vector<int>&L,vector<int>&R,vector<int>V)
    {
        q.push(s);
        vis[s]=true;
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=fir[u];i;i=e[i].nex)
            {
                if(!e[i].w)continue;
                int v=e[i].v;
                if(!vis[v])q.push(v),vis[v]=true;
            }
        }
        for(int it:V)if(vis[it])L.push_back(it);else R.push_back(it);
        memset(vis,0,sizeof vis);
        return;
    }
    void solve(vector<int>V)
    {
        if(V.size()<2)return;
        fprintf(stderr,"solve:\n");
        for(int it:V)fprintf(stderr,"%d ",it);
        fprintf(stderr,"\n");
        init(V[0],V[1]);
        int val=dinic();
        fprintf(stderr,"dinic: %d\n",val);
        T[V[0]].push_back(make_pair(V[1],val));
        T[V[1]].push_back(make_pair(V[0],val));
        vector<int>L,R;
        getV(L,R,V);
        // assert(L.size()<V.size()&&R.size()<V.size()&&L.size()+R.size()==V.size());
        solve(L),solve(R);
        return;
    }
public:
    int ans[N][N];
private:
    void get_ans(int s)
    {
        memset(ans[s],0x7f,sizeof ans[s]);
        q.push(s);
        vis[s]=true;
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(auto[v,w]:T[u])if(!vis[v])ans[s][v]=min(ans[s][u],w),q.push(v),vis[v]=true;
        }
        memset(vis,0,sizeof vis);
        return;
    }
public:
    void build(int n)
    {
        for(int i=1;i<=n;i++)T[i].clear();
        vector<int>V;
        for(int i=1;i<=n;i++)V.push_back(i);
        solve(V);
        for(int i=1;i<=n;i++)get_ans(i);
        return;
    }
}GMHT;
int u[M],v[M],w[M];
bool G[N][N];//注意使用邻接矩阵，直接暴力加边，最后边数可能达到 $m^n$。
stack<int>stk;
set<int>S,T;
bool del[N];
inline void solve()
{
    // static int id=0;
    // id++;
    int n,m;
    scanf("%d%d",&n,&m);
    ent=1;
    for(int i=1;i<=n;i++)fir[i]=0,del[i]=false;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",u+i,v+i,w+i);
        add(u[i],v[i],w[i]);
    }
    // if(id==115&&n==5)
    // {
    //  printf("%d|%d\\n",n,m);
    //  for(int i=1;i<=m;i++)printf("%d|%d|%d\\n",u[i],v[i],w[i]);
    //  exit(0);
    // }
    GMHT.build(n);
    int g=0;
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)g=__gcd(g,GMHT.ans[i][j]);
    if(g>1||g==0)
    {
        puts("1");
        printf("%d\n",n);
        for(int i=1;i<=n;i++)printf("%d ",i);
        putchar(10);
        return;
    }
    S.clear(),T.clear();
    for(int i=1;i<=n;i++)S.insert(i);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)G[i][j]=0;
    for(int i=1;i<=m;i++)if(w[i]&1)G[u[i]][v[i]]^=1,G[v[i]][u[i]]^=1;
    bool f;
    do
    {
        f=false;
        for(int i=1;i<=n;i++)
        {
            if(del[i])continue;
            bool cnt=0;
            for(int j=1;j<=n;j++)if(!del[j])cnt^=G[i][j];
            if(cnt)
            {
                for(int u=1;u<=n;u++)for(int v=u+1;v<=n;v++)if(G[i][u]&&G[i][v]&&!del[u]&&!del[v])G[u][v]^=(G[i][u]&G[i][v]),G[v][u]^=(G[i][u]&G[i][v]);
                S.erase(i);
                stk.push(i);
                del[i]=f=true;
                fprintf(stderr,"delete: %d\n",i);
                break;
            }
        }
    }
    while(f);
    fprintf(stderr,"delete finished\n");
    while(!stk.empty())
    {
        int u=stk.top();stk.pop();
        fprintf(stderr,"reset: %d\n",u);
        int cnt=0;
        for(int v=1;v<=n;v++)
        {
            if(!G[u][v])continue;
            fprintf(stderr,"%d->%d\n",u,v);
            cnt^=(S.find(v)!=S.end());
        }
        if(cnt)swap(S,T);
        S.insert(u);
        for(int it:S)fprintf(stderr,"%d ",it);
        fprintf(stderr,"\n");
        for(int it:T)fprintf(stderr,"%d ",it);
        fprintf(stderr,"\n");
    }
    puts("2");
    printf("%d\n",S.size());
    for(int it:S)printf("%d ",it);
    putchar(10);
    printf("%d\n",T.size());
    for(int it:T)printf("%d ",it);
    putchar(10);
    return;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

:::