首页 > 代码库 > 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行列匹配+排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。