自动搬运

查看原文

来自洛谷，原作者为

	mlvx 喵

搬运于2025-08-24 22:53:04，当前版本为作者最后更新于2024-09-07 16:17:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

一个 $n\times n$ 的方阵，里面有 $m$ 个点，选中至少一个点，使得每行每列被选中点数相同。

分析

方格中对于行与列需要满足某种特征的题面，往往可以建图来解决。

每一行，每一列，分别对应一个编号。

例如 $(u,v)$ 处有一个点，那我们就把 $u$ 和 $v+n$ 连边。

此时我们发现，这个图是个二分图，虽然在本题中并没有什么用。

现在问题就变成了找出图的一个子图，使得其中所有点的度数的奇偶性相同。

环上的点的度数都是偶数，故找出环即为找出偶数解的情况。

void dfs1(int x){
	vis[x]=1;
	for(auto[y,w]:g[x])if(!Vis[w]){
		Vis[w]=1,last[y]=x,from[x]=w;
		if(vis[y]){
			int cnt=0;puts("TAK");
			for(int tmp=last[y];tmp!=y;)++cnt,tmp=last[tmp];
			cout<<cnt+1<<'\n'<<from[y]<<' ';
			for(int tmp=last[y];tmp!=y;)cout<<from[tmp]<<' ',tmp=last[tmp];
			exit(0);
		}dfs1(y);
	}
}

不难发现图中如果没有环，那么这个图就是个森林。

由于叶子的度数是 $1$，所以所有点的度数都得是奇数。

注意到想要改变度数只能改变这个节点和其父亲的连边情况，所以从叶子节点向上进行改变即可。

void dfs2(int x){
	vis[x]=1;
	for(auto[y,w]:g[x])if(!vis[y])dfs2(y),dp[y]||(dp[x]^=1,ans[y]=w);
}

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=5e5+10;
int n,m,u,v,vis[N<<1],from[N<<1],last[N<<1],dp[N<<1],ans[N<<1],Vis[M];vector<pair<int,int>>g[N<<1];
void dfs1(int x){
	vis[x]=1;
	for(auto[y,w]:g[x])if(!Vis[w]){
		Vis[w]=1,last[y]=x,from[x]=w;
		if(vis[y]){
			int cnt=0;puts("TAK");
			for(int tmp=last[y];tmp!=y;)++cnt,tmp=last[tmp];
			cout<<cnt+1<<'\n'<<from[y]<<' ';
			for(int tmp=last[y];tmp!=y;)cout<<from[tmp]<<' ',tmp=last[tmp];
			exit(0);
		}dfs1(y);
	}
}void dfs2(int x){
	vis[x]=1;
	for(auto[y,w]:g[x])if(!vis[y])dfs2(y),dp[y]||(dp[x]^=1,ans[y]=w);
}int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>u>>v,g[u].push_back({v+n,i}),g[v+n].push_back({u,i});
	for(int i=1;i<=(n<<1);i++)if(!vis[i])dfs1(i);
	memset(vis,0,sizeof vis);
	for(int i=1;i<=(n<<1);i++)if(!vis[i]){dfs2(i);if(!dp[i])return puts("NIE"),0;}
	puts("TAK");int cnt=0;
	for(int i=1;i<=(n<<1);i++)if(ans[i])++cnt;
	cout<<cnt<<'\n';
	for(int i=1;i<=(n<<1);i++)if(ans[i])cout<<ans[i]<<' ';
	return 0;
}