[ABC317G] Rearranging

灰鲭鲨 / 2023-09-04 / 原文

Problem Statement

There is a grid with $N$ rows and $M$ columns. The square at the $i$-th row from the top and the $j$-th column from the left contains the integer $A_{i,j}$.
Here, the squares contain $M$ occurrences of each of $1,\ldots,N$, for a total of $NM$ integers.

You perform the following operations to swap the numbers written on the squares.

For $i=1,\ldots,N$ in this order, do the following.
- Freely rearrange the numbers written in the $i$-th row. That is, freely choose a permutation $P=(P_{1},\ldots,P_{M})$ of $1,\ldots,M$, and replace $A_{i,1},\ldots,A_{i,M}$ with $A_{i,P_{1}},\ldots,A_{i,P_{M}}$ simultaneously.

Your goal is to perform the operations so that each column contains each of $1,\ldots,N$ once. Determine if this is possible, and if so, print such a resulting grid.

盲猜没有无解。

一列一列处理，每次算出一列。而某一列可以建出二分图计算。如果第 $i$ 行存在数 $j$ 就从左部 $i$ 向右部 $j$ 连一条边，问题变为找一个匹配，匈牙利即可（为什么大家都Dinic 的）

现在要证明不存在无解情况，也就是不存在某一时刻二分图不存在完美匹配，转成Hall 定理的话，某 $k$ 行出现过的不同的数一定超过 $k$，设剩下 $m$ 列没处理，那么每种数最多出现 $m$ 次， $k$ 行中共有 $km$ 个数，所以至少会有 $k$ 个不同的数，二分图一定存在完美匹配。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,a,b,c,vs[N],st[N],tp,idx,dfn[N],low[N];
struct graph{
	int hd[N],e_num;
	struct edge{
		int v,nxt;
	}e[N<<1];
	void add_edge(int u,int v)
	{
		e[++e_num]=(edge){v,hd[u]};
		hd[u]=e_num; 
		e[++e_num]=(edge){u,hd[v]};
		hd[v]=e_num; 
	}
}g,h;
int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++idx;
	st[++tp]=x;
	for(int i=g.hd[x];i;i=g.e[i].nxt)
	{
		int v=g.e[i].v;
		if(!dfn[v])
		{
			tarjan(v);
			low[x]=min(low[x],low[v]);
			if(low[v]==dfn[x])
			{
				++n;
				while(st[tp]^v)
					h.add_edge(n,st[tp--]);
				h.add_edge(n,st[tp--]);
				h.add_edge(x,n);
			}
		}
		else
			low[x]=min(low[x],dfn[v]);
	}
}
void dfs(int x,int y)
{
	st[++tp]=x;
	if(x==c)
	{
		for(int i=1;i<=tp;i++)
			vs[st[i]]=1;
		return;
	}
	for(int i=h.hd[x];i;i=h.e[i].nxt)
		if(h.e[i].v^y)
			dfs(h.e[i].v,x);
	--tp;
}
int main()
{
	n=read(),m=read(),a=read(),b=read(),c=read();
	for(int i=1,u,v;i<=m;i++)
		g.add_edge(read(),read());
	tarjan(a);
	dfs(a,0);
	for(int i=h.hd[b];i;i=h.e[i].nxt)
		if(vs[h.e[i].v])
			return puts("Yes"),0;
	puts("No");
}