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");
}