`
promiser
  • 浏览: 76335 次
  • 性别: Icon_minigender_1
  • 来自: 广州
文章分类
社区版块
存档分类
最新评论

bzoj1059: [ZJOI2007]矩阵游戏

    博客分类:
  • oi
阅读更多

在一个矩阵中任意一个黑色点都可以通过旋转到任意一个位置,所以只要尽可能的选择一些黑点,让每一行&每一列都用且仅用一次,二分匹配就显然了

 

以前打过一种快速二分匹配算法,但现在忘,只能打普通的二分匹配算法。那种快速二分匹配算法是用了网络流的思想,用BFS重标号,多路增广

 

const int N = 210;
int n, Dat[N][N], Link[N];
bool Vis[N];

inline void Input() {
	clr(Dat, 0), clr(Link, 0);
	scanf("%d",&n);
	For(i, 1, n)
		For(j, 1, n) Dat[i][j] = (getchar(), getchar()) - 48;
}

inline bool Find(int x) {
	For(i, 1, n)
		if (Dat[x][i] && !Vis[i]) {
			Vis[i]=1;
			if (!Link[i] || Find(Link[i])) {
				Link[i]=x;
				return 1;
			}
		}
	 return 0;
}
inline void Solve() {
	For(i, 1, n) {
		clr(Vis, 0);
		if (!Find(i)) {
			printf("%s\n","No");
			return;
		}
	}
	printf("%s\n","Yes");
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1059");
	#endif
	int T;
	for(scanf("%d", &T); T--;) {
		Input();
		Solve();
	}
	return 0;
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics