题目描述
琪露诺调查之后，发现一共有 \(n\) 种不同的卡片，每种卡片的数量总共恰好是 \(n\) 张，有 \(n\) 个人购买了这些卡片，每个人都恰好买了 \(n\) 张卡片，并且可能会买到相同种类的卡片。
但是琪露诺想要让每个人都正好持有 \(n\) 种卡片，于是她把这 \(n\) 个人聚集在一起，想要通过卡片交换的形式达成她的目的。
琪露诺每次会选择两个人持有的某张卡片进行交换，直到每个人都正好持有 \(n\) 种卡片为止。
由于每次交换都会减少卡片上的魔力，所以琪露诺想要每张卡片最多被交换一次。
但是她对如何进行交换犯了难，于是她转而寻求你的帮助。
你需要告诉她交换的过程，或者告诉她不存在这样的方案。
题解
首先发现，如果我们可以通过交换每行的数的顺序，使得每一列的数都不同，最后只要交换\((i,j)\)和\((j,i)\)就可以满足条件了
匹配就可以考虑建图，每行向它所拥有的颜色连边，跑最大流，跑\(n\)遍二分图匹配，就可以求出每个点去到哪一列，不会出现无解情况，可以用\(hall\)定理证明，假设现在已经跑了\(i\)遍二分图匹配，那么每个点的度数都会变为\(n-i\)，假设选出左边的\(x\)个点，那么根据鸽巢原理，可以发现右边与之相连的点一定\(\ge x\)，故一定存在完美匹配
\(\text{code}\)
#include<cstdio>
#include<queue>
using namespace std;
void read(int &res)
{
res=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=5e2+100,M=N*N+10;
int n,m,s,t,st[N+10],tot;
struct edge
{
int to,last,flow,id;
}e[M<<1|1];
void add(int a,int b,int c,int id)
{
e[++tot].to=b;
e[tot].last=st[a];
e[tot].flow=c;
e[tot].id=id;
st[a]=tot;
}
void Add(int a,int b,int c,int id){add(a,b,c,id),add(b,a,0,id);}
queue<int> q;
int cur[N+10],dep[N+10];
bool bfs(int s,int t)
{
for(int i=s;i<=t;i++) cur[i]=st[i],dep[i]=-1;
dep[s]=0,q.push(s);
for(int u;!q.empty();)
{
u=q.front(),q.pop();
for(int i=st[u],v;i!=0;i=e[i].last)
{
v=e[i].to;
if(!e[i].flow||dep[v]!=-1) continue;
dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t]!=-1;
}
int dfs(int flow,int u,int t)
{
if(u==t) return flow;
for(int i=cur[u],v;i!=0;i=e[i].last)
{
cur[u]=i,v=e[i].to;
if(!e[i].flow||dep[v]!=dep[u]+1) continue;
int res=dfs(min(flow,e[i].flow),v,t);
if(res)
{
e[i].flow-=res,e[i^1].flow+=res;
return res;
}
}
return 0;
}
int dinic(int s,int t)
{
int res=0;
while(bfs(s,t))
{
int inc;
while(inc=dfs(1,s,t))
res+=inc;
}
return res;
}
int a[N+10][N+10],id[N+10][N+10];
int main()
{
// freopen("a.in","r",stdin);
int T;
read(T);
for(;T--;)
{
read(n);
tot=1;
int s=0,t=n*2+1;
for(int i=s;i<=t;i++) st[i]=0;
int beg=0,ed=0;
for(int i=1;i<=n;i++) Add(s,i,1,0);
ed=tot;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
read(a[i][j]);
Add(i,n+a[i][j],1,j);
}
beg=tot;
for(int i=1;i<=n;i++) Add(n+i,t,1,0);
for(int i=1;i<=n;i++)
{
for(int i=2;i<=ed;i+=2) e[i].flow=1,e[i^1].flow=0;
for(int i=beg+1;i<=tot;i+=2) e[i].flow=1,e[i^1].flow=0;
dinic(s,t);
for(int k=1;k<=n;k++)
for(int j=st[k];j!=0;j=e[j].last)
{
if(e[j].to<=n) continue;
if(e[j].flow==0&&e[j^1].flow==1)
e[j^1].flow=0,id[k][i]=e[j].id;
}
}
printf("%d\n",n*(n-1)/2);
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
printf("%d %d %d %d\n",i,id[i][j],j,id[j][i]);
}
return 0;
}