本文共 2394 字，大约阅读时间需要 7 分钟。

题目：

Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?

Input

There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.

Output

For each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.

Sample Input

20 11 021 01 0

Sample Output

1R 1 2-1

思路：

将这个方阵抽象成一个邻接矩阵，0表示不存在边，1表示存在边，题目的目标状态是对角线元素为1，所以表明，每一横行和每一竖行都必须有边，否则不能转换成目标状态。

此题可以通过匈牙利算法来实现匹配，然后遍历来实现交换元素。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=105;int n;int a[maxn][maxn];int match[maxn];int vis[maxn];bool Find(int x){    for (int i=1;i<=n;i++)    {        if(a[x][i]&&!vis[i])        {            vis[i]=1;            if(match[i]==-1||Find(match[i]))            {                match[i]=x;                return true;            }        }    }    return false;}int alor(){    int sum=0;    for (int i=1;i<=n;i++)    {        memset (vis,0,sizeof(vis));        if(Find(i)) sum++;    }    return sum;}int main(){    while(scanf("%d",&n)!=EOF)    {        memset (match,-1,sizeof(match));        for (int i=1;i<=n;i++)        {            for (int j=1;j<=n;j++)            {                scanf("%d",&a[i][j]);            }        }        if(alor()!=n)        {            printf("-1\n");            continue;        }        else        {            int cnt=0;            int opa[maxn*maxn],opb[maxn*maxn];            for (int i=1;i<=n;i++)            {                if(match[i]==i) continue;                for (int j=i+1;j<=n;j++)                {                    if(match[j]==i)                    {                        opa[cnt]=i,opb[cnt]=j;                        swap(match[i],match[j]);                        cnt++;                        break;                    }                }            }            printf("%d\n",cnt);            for (int i=0;i
      
     
    
   

转载地址：http://mwoen.baihongyu.com/