我们记一次操作为一个二元组(i,j)
考虑矩阵中的元素a，它原来的位置是(x,y)，则经过操作(i,j)后等价于分别对x和y做一次置换映射，这个置换映射就是s0=(i j)，是一个轮换
因此每一个操作都可以看做一个轮换，所以操作并起来就是这些轮换的乘积，记为s，它还是一个置换映射
如果a原来的位置是(x,y)，经过这一系列操作，最终的位置是(s(x),s(y))
对于每一个非零元素a(x,y)，我们只要要求s(x)<=s(y)即可，当x=y时，显然有s(x)=s(y)，而当x!=y时，有s(x)!=s(y)
因此只需使在x!=y时，s(x)<s(y)即可
我们可以建立一个拓扑排序模型，将1,2,...,n做拓扑排序，记它们在拓扑序列中的位置为s(1),s(2),...,s(n).
对于每一个非零元素a(x,y)，且x!=y，必须满足s(x)<s(y)，即从y到x添一条有向边
如果不能拓扑排序，则无解。否则得到s，把它拆成轮换的乘积，然后再把轮换拆成对换的乘积即可
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
bool d[120][120];
int n,m,in[120],s[120],x[120],y[120];
bool b[120];
int main(void)
{
int i,j,k,t;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
in[i]=0;
b[i]=true;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
d[i][j]=false;
scanf("%d",&t);
if (i!=j&&t!=0)
{
d[i][j]=true;
in[j]++;
}
}
for(i=1;i<=n;i++)
{
k=0;
for(j=1;j<=n;j++)
if (in[j]==0)
{
k=j;
break;
}
if (k==0) break;
s[k]=i;
in[k]--;
for(j=1;j<=n;j++)
if (d[k][j])
in[j]--;
}
if (i<=n)
{
printf("%d\n",-1);
return 0;
}
m=0;
for(i=1;i<=n;i++)
{
if (!b[i]) continue;
b[i]=false;
if (s[i]==i) continue;
for(j=s[i];j!=i;j=s[j])
{
b[j]=false;
m++;
x[m]=i;
y[m]=j;
}
}
printf("%d\n",m);
for(i=1;i<=m;i++)
printf("%d %d\n",x[i],y[i]);
return 0;
}
posted on 2010-10-11 13:34
zxb 阅读(284)
评论(0) 编辑 收藏 引用