专栏文章

CF2147H Maxflow GCD Coloring

XXiaoShanYunPan
CF2147H题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@minszbzg
此快照首次捕获于
2025/12/02 07:51
3 个月前
此快照最后确认于
2025/12/02 07:51
3 个月前
查看原文
2025-10-16 修改了一处笔误。
jiangly 讲的。

题意

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

小剧场

jiangly：那这个题其实，就看上去它就很很很……很难，看上去它就很……很复杂。
jiangly：就这种题，我觉得大家不知道就是……能不能有这种……感觉了就是……实际上也是题做多了就是，你感觉这个题要么答案是 11 要么答案是 22 不然它就做不了，对吧有这样一种感觉。
jiangly：就是……就简单来说就是……如果它要分 33 份我就不会做了，所以它一定是分 22 份，嗯懂我意思吗。

题解

考虑 cc 的最小值一定是 11 或 22，证明见后续构造。
当 c=1c=1 时，可以直接使用最小割树判断。
当 c=2c=2 时，考虑令 d=2d=2，我们要使所有点对间的最小割/最大流为偶数。
这里有一个结论：去掉所有偶数边后，若每个点的度数均为偶数，则任意两点间的最小割也为偶数。
jiangly 没有讲这个东西为什么对，或许很显然吧。
一种证明
考虑满足上述条件时始终存在欧拉回路。
对于一个点对 (s,t)(s,t)，欧拉回路上一定可以分出若干 s→t→ss\rightarrow t\rightarrow s 的路径。
对于每一段这样的路径，我们必然需要割掉至少一条边，最小割也包含在内，因此最小割必然割掉偶数条边，由于边的容量全为奇数，所以此时最小割为偶数。
考虑加回偶数边，这些边无论怎么加都不会影响原本的最小割，产生的新的割边也不影响答案的奇偶性，所以最小割仍为偶数。
证毕。
现在我们将所有偶数边去掉，对于剩下的图，我们需要给每个点染色，使得每种颜色的导出子图上，所有点的度数均为偶数。
考虑增量构造，我们每次加入一个点并决定其颜色，为方便下设两种颜色的点集分别为 A,BA,B。
先通过递归，每次删除一个奇数度数的点 uu，同时对于所有点对 (v,w)(v,w) 连边，其中 v,wv,w 都是 uu 的邻居，直到最后剩下的点全为偶数度数（显然至多删成一个点就不会再删了），将它们全部加入点集 AA。
考虑往回加入点 uu，由于点 uu 的邻居有奇数个，则必然有一个点集中包含奇数个 uu 的邻居，设该集合为 SS，另一个为 TT。
结论：我们应当把 uu 加入 TT。
这是因为原本 S,TS,T 都满足其中所有点的度数均为偶数，而在加入 uu 之后，我们需要删除所有在这时删除的边。
显然，此时度数会发生变化的点只有 uu 和 uu 的邻居，对于 uu 而言，它显然只能加入 TT。
再考察所有 uu 的邻居来确定这是对的，分别对两个集合内的邻居来看：
对于 SS，其中有奇数个点是 uu 的邻居，由于 uu 没有加入 SS，SS 中所有 uu 的每个邻居的度数减少了 SS 中 uu 的邻居数 −1-1，这无疑是一个偶数。
对于 TT，同上分析，所有 uu 的邻居的度数减少了一个奇数，其奇偶性发生了改变，然而 uu 加入之后每个 uu 的邻居多了一条边，度数又变回来了。
所以上述构造方案是合法的，我们始终能够构造出这样的一组解。
代码
人傻常数大，写得还丑，看个乐子就好。
然而这里有个细节是在构造时会出现巨量的重边，甚至到 long long 都存不下的地步，但是我们只关注奇偶性，所以可以存成 bool。
CPP
/*
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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...