首页 > 代码库 > hdu2818行列匹配+排序

hdu2818行列匹配+排序

题意:给定一个矩阵,矩阵上有的数字是1,有的是0,给定两种操作,交换某两行或者某两列,问是否能置换出对角线为1的矩阵

题解:能够置换出对角线是1的矩形要求有n个1既不在同一行也不再同一列,即行列匹配,所以匹配很简单,关键是怎么求出交换的过程,

cx[i] 表示第i行与第cx[i]列匹配,即第i行要变成第cx[i]行
所以将cx从小到大排序,记录交换的的下标,那么就是所需要的结果。因为要求交换次数不能超过1000,所以用选择排序

 1 #include <stdio.h> 2 #include <string.h> 3 const int N =    100 + 10; 4 int Map[N][N]; 5 int cx[N],cy[N]; 6 int a[N]; 7 bool vis[N]; 8 int n; 9 struct node10 {11     int x,y;12 }ans[1111];13 bool dfs(int u)14 {15     for(int i=0; i<n; ++i)16     {17         if(!vis[i] && Map[u][i])18         {19             vis[i] = true;20             if(cy[i]==-1 || dfs(cy[i]))21             {22                 cy[i] = u;23                 cx[u] = i;24                 return true;25             }26         }27     }28     return false;29 }30 int MaxMatch()31 {32     memset(cx, -1, sizeof(cx));33     memset(cy, -1, sizeof(cy));34     int cnt = 0;35     for(int i=0; i<n; ++i)36     {37         if(cx[i] == -1)38         {39             memset(vis, 0, sizeof(vis));40             cnt += dfs(i);41         }42     }43     return cnt;44 }45 int main()46 {47     int i,j;48     while(scanf("%d",&n)!=EOF)49     {50         for(i=0; i<n; ++i)51             for(j=0; j<n; ++j)52                 scanf("%d",&Map[i][j]);53         if(MaxMatch() == n)  // 那么可以置换出对角线是1的矩形54         {    55             int cnt = 0;56             for(i=0; i<n; ++i)57                 a[i] = cx[i];//cx[i] 表示第i行与第cx[i]列匹配,即第i行要变成第cx[i]行58             //所以将cx从小到大排序,记录交换的的下标,那么就是所需要的结果59             for(i=0; i<n-1; ++i)60             {61                 int index = i;62                 for(j=i+1; j<n; ++j)63                 {64                     if(a[j] < a[index])65                         index = j;66                 }67                 if(index != i)68                 {69                     int tmp = a[i];70                     a[i] = a[index];71                     a[index] = tmp;72                     ans[cnt].x = i;73                     ans[cnt++].y = index;74                 }75             }76             printf("%d\n",cnt);77             for(i=0; i<cnt; ++i)78                 printf("R %d %d\n",ans[i].x+1, ans[i].y+1);79         }80         else81             puts("-1");82     }83     return 0;84 }85 86 87 /*88 389 0 1 090 0 0 191 1 0 092 */

 

hdu2818行列匹配+排序