首页 > 代码库 > bzoj 1059 矩阵游戏
bzoj 1059 矩阵游戏
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1059
题解：
很玄学的问题……
因为不同行或者不同列的格子，交换仍然不同行或者不同列
所以把问题转化为从黑格子里选n个，它们的横纵坐标都不相同
然后二分图匹配……两个子集分别是横坐标和纵坐标，如果求出的最大匹配为n，则成立，否则不成立
1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 410 4 int n,cnt,match[MAXN],map[MAXN][MAXN],ans; 5 bool check[MAXN]; 6 bool Hungary(int u) 7 { 8 for(int i=1;i<=n;i++) 9 {10 if(!check[i]&&map[u][i])11 {12 check[i]=true;13 if(!match[i]||Hungary(match[i]))14 {15 match[i]=u;16 return true;17 }18 }19 }20 return false;21 }22 int main()23 {24 int t;25 scanf("%d",&t);26 while(t--)27 {28 ans=0;29 memset(match,false,sizeof(match));30 memset(map,0,sizeof(map));31 scanf("%d",&n);32 for(int i=1;i<=n;i++)33 for(int j=1;j<=n;j++)34 scanf("%d",&map[i][j]);35 for(int i=1;i<=n;i++)36 {37 memset(check,false,sizeof(check));38 if(Hungary(i))ans++;39 }40 if(ans==n)printf("Yes\n");41 else printf("No\n");42 }43 return 0;44 }
bzoj 1059 矩阵游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。