[CF2147H] Maxflow GCD Coloring 题解

· · 题解

观察到这题很复杂，我们猜测答案很小，不妨猜 ans\in\{1,2\}。

对于 ans=1 可以最小割树判断（注意图可以不连通）

对于 ans=2，我们发现首先可以不管边权为偶数的边，然后注意到对于其中一个导出子图，其合法的充要条件为：

如果图是一个欧拉图，那么对于每个最小割 cut(S,T) 之间都一定会存在若干条欧拉回路，于是必须割掉偶数条边。那么这个图就满足 \forall x,y,2|cut(x,y)。

同时这也是必要条件，如果存在 S,T 使它们之间不存在欧拉回路，那么它们之间存在奇数条路径，而且图中边都是奇数，于是不满足 2|cut(x,y)。

那么相当于让我们将图分为两个导出欧拉子图。

令 p_i 为点 i 所属集合的编号 \{0,1\}。那么限制可以使用异或方程组表示。

即在导出子图中每个点度数为偶：\forall x,\oplus_{(x,y)\in E} (p_x\oplus p_y\oplus 1)=0。

考虑证明这个异或方程组一定有解。注意此时方程中的 0,1 仅代表系数，而不是 p 值。

考虑反证法，令 f(x,i) 表示方程 x 在消元后第 i 项的系数，令常数项为第 0 项。

无解即存在点集 S，使 x\in S,\oplus f(x,0)=1,f(x)=\{1,0,\dots,0\}。

考虑消元时，将 S 内所有方程 x 的系数消为 0 的过程。不妨将每个点的方程看作若干方程 (x,y)\in E,p_x\oplus p_y =1 的组合。那么首先 S 内的所有边的方程可以一一抵消。

只剩下若干形如 x\in S,y\not \in S,p_x\oplus p_y=1 的方程，考虑对于一个 p_x 需要找到另一个含 p_x 的方程来消掉它，于是仅看 x\in S 含 p_x 的方程成对出现，于是所有未被抵消的方程总共有偶数个，异或后常数项为 0，与假设矛盾。于是方程组一定有解。

高斯消元即可。对于第 k 项每次选择第 k 项系数为 1 的且未被选择过的一行 i，将 i 行与其它行异或，即可得对角线矩阵，解为常数项。

还有一种构造解法，比较需要脑子。考虑增 / 减量构造，将图分为两个导出欧拉子图。

首先，取一个图中度数为奇数的点 x 删去，并将与 x 相邻的点两两连边。

重复这个过程直到图中只有度数为偶数的点。将图中剩余点分入集合 A。

然后，将删去的点依次加入，并将之前多两两连的边撤销。

对于被删去的点 x，因为其度数为奇，于是两个集合 A,B 中恰有一个使加入 x 后，x 的度数为偶。

我们将 x 加入这个集合，不妨令其为 A。那么 A 中与 x 相邻的点的度数 c 首先都 +1，然后撤销两两之间的边，度数减少 c-1,2\nmid c-1，其奇偶性再次变化，于是 A 中的所有点在加入 x 后度数依然为偶数。

考虑没有加入 x 的 B 集合，其中与 x 相邻的点个数 c 为奇数，于是撤销两两之间的边后，度数减少 c-1,2|c-1，故其奇偶性也不会变。

综上，最后 A,B 中的所有点度数均为偶数，且恰好覆盖原来所有的点和 A,B 内的边。构造完成。

代码使用高斯消元方法。

#include<bits/stdc++.h>
#define rg register int
#define fo(i,l,r) for(rg i=(l);i<=(r);i++)
#define dfo(i,r,l) for(rg i=(r);i>=(l);i--)
#define fe(i,x) for(rg i=hd[x];i;i=nex[i])
#define frein freopen("in.txt","r",stdin);
#define freout freopen("out.txt","w",stdout);
#define fre(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout);
#define eb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
#define vi vector<int>
#define db double
#define i8 __int128
#define ll long long
using namespace std;
bool deb=1;
void ck_(){cerr<<"\n";}
template<typename T,typename ...R>
void ck_(T x,R... y){if(!deb)return;cerr<<x<<" ";ck_(y...);}
void Bz_(){if(deb)cerr<<"------------------------------\n";}
#define ck(x...) ck_(x)
#define Bz Bz_()
#define outa(l,r,a) {if(deb){fo(II,l,r)cerr<<a[II]<<" ";cerr<<"\n";}}
auto St=chrono::high_resolution_clock::now();
#define gettime() (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()-St).count())
const int N=55,M=6005;
int Task,n,m,x,y,z,Q;
struct nd{int p,v;};vector<nd>e[N];
struct edge{int x,y,z;}eg[M];
int sum=1,to[M],nex[M],hd[N],ef[M];
void ado(int x,int y,int f){to[++sum]=y,nex[sum]=hd[x],hd[x]=sum,ef[sum]=f;}
void add(int x,int y,int f){ado(x,y,f),ado(y,x,0);}
#define inf 1e9
int S,T,p[N];
int t,w,q[M<<5],dis[N],cur[N];
bool bfs()
{
    fo(i,1,n)dis[i]=inf,cur[i]=hd[i];
    q[t=w=1]=S,dis[S]=0;
    while(t<=w)
    {
        int x=q[t++];
        fe(i,x)if(ef[i]&&dis[to[i]]==inf)
        {
            dis[to[i]]=dis[x]+1,q[++w]=to[i];
        }
    }
    return dis[T]!=inf;
}
int dfs(int x,int fl)
{
    if(x==T)return fl;
    int s=0,t;
    for(rg i=cur[x];i&&fl;i=nex[i])
    {
        cur[x]=i;
        if(ef[i]&&dis[to[i]]==dis[x]+1)
        {
            t=dfs(to[i],min(fl,ef[i]));
            if(t==0)dis[to[i]]=-1;
            ef[i]-=t,ef[i^1]+=t,s+=t,fl-=t;
        }
    }
    return s;
}
int dinic(int SS,int TT)
{
    S=SS,T=TT;sum=1;
    fo(i,1,n)hd[i]=0;
    fo(i,1,m)add(eg[i].x,eg[i].y,eg[i].z),add(eg[i].y,eg[i].x,eg[i].z);
    int ans=0;
    while(bfs())ans+=dfs(S,inf);
    return ans;
}
void wk(int l,int r)
{
    if(l>=r)return;
    int mxf=dinic(p[l],p[r]);
    e[p[l]].eb(nd{p[r],mxf}),e[p[r]].eb(nd{p[l],mxf});
    vi le,ri;
    fo(i,l,r)
    {
        if(dis[p[i]]==inf)le.eb(p[i]);
        else ri.eb(p[i]);
    }
    int i=l,md;
    for(int o:le)p[i++]=o;md=i;
    for(int o:ri)p[i++]=o;
    wk(l,md-1),wk(md,r);
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int ans;
void getans(int o,int x,int fa,int d)
{
    if(o!=x)ans=ans==0?d:gcd(ans,d);
    for(nd y:e[x])if(y.p!=fa)getans(o,y.p,x,min(d,y.v));
}
bitset<N>b[N];
void gauss()
{
    fo(k,1,n)
    {
        int x=0;
        fo(i,k,n)if(b[i][k]==1)x=i;
        swap(b[k],b[x]);
        fo(i,1,n)if(i!=k&&b[i][k]==1)b[i]^=b[k];
    }
}
void solve()
{
    cin>>n>>m;
    fo(i,1,m)cin>>x>>y>>z,eg[i]=edge{x,y,z};
    fo(i,1,n)e[i].clear();
    fo(i,1,n)p[i]=i;wk(1,n);
    ans=0;
    fo(i,1,n)getans(i,i,0,inf);
    if(ans>=2||ans==0)
    {
        cout<<"1\n"<<n<<"\n";
        fo(i,1,n)cout<<i<<" ";cout<<"\n";
        return;
    }
    fo(i,1,n)b[i].reset();
    fo(i,1,m)if(eg[i].z&1)
    {
        x=eg[i].x,y=eg[i].y;
        b[x].flip(x),b[x].flip(y),b[x].flip(0);
        b[y].flip(y),b[y].flip(x),b[y].flip(0);
    }
    gauss();
    int c0=0,c1=0;
    fo(i,1,n)b[i][0]?++c1:++c0;
    cout<<"2\n";
    cout<<c0<<"\n";fo(i,1,n)if(b[i][0]==0)cout<<i<<" ";cout<<"\n";
    cout<<c1<<"\n";fo(i,1,n)if(b[i][0]==1)cout<<i<<" ";cout<<"\n";
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>Task;
    while(Task--)solve();
    return 0;
}