首页 > 代码库 > 【bzoj1059】 ZJOI2007—矩阵游戏
【bzoj1059】 ZJOI2007—矩阵游戏
http://www.lydsy.com/JudgeOnline/problem.php?id=1059 (题目链接)
题意
一个01矩阵，可以任意交换两行或两列，问能否经过若干次交换后使主对角线全为1。
Solution
hzwer：同行同列的点无论经过多少次变换仍然同行或同列，所以题目可转换为能不能找到n个互相不同行或同列的点。
代码
// bzoj1059#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 10000000#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=300;int p[maxn],vis[maxn],f[maxn][maxn];int n,cnt;bool match(int x) { for (int i=1;i<=n;i++) if (vis[i]!=cnt && f[x][i]) { vis[i]=cnt; if (!p[i] || match(p[i])) {p[i]=x;return 1;} } return 0;}int main() { int T;scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&f[i][j]); int ans=0;cnt=0; memset(p,0,sizeof(p)); memset(vis,0,sizeof(vis)); for (int i=1;i<=n;i++) { cnt++; if (match(i)) ans++; } if (ans==n) puts("Yes"); else puts("No"); } return 0;}
【bzoj1059】 ZJOI2007—矩阵游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。