BZOJ 1059 [ZJOI2007]矩阵游戏

starli posted @ 2016年2月03日 19:17 in 二分图 , 162 阅读

类似于这道题的题似乎以前多面体在codevs月赛里出过

不管怎么动 处在同一列的格子总是处在同一列 行同理 则问题转化成要找到一些黑格子 其中任意两个都不在同一行或同一列

把行号看成二分图的一部 列看成另一部 那么就变成了一个二分图匹配的问题 对于每一个f[i][j]是黑的 我们连边(i,j),之后匈牙利算法(不会的百度一下或者问学长)搞一下就好了

我在打匈牙利算法的时候 忘记在每一轮的匹配中加上这一轮匹配是否用过的标记 于是就wa了……

还有注意边的数比较多……

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=41000;
int e[N],pre[N],now[N],T,n,tail,to[N],from[N],vis[N],tmp;
bool flag;
void add(int u,int v){e[++tail]=v;pre[tail]=now[u];now[u]=tail;}
bool hungary(int a){
	for(int i=now[a];i;i=pre[i]){
		if(vis[e[i]]) continue;else vis[e[i]]=1;
		if(!from[e[i]] || hungary(from[e[i]])) {from[e[i]]=a,to[a]=e[i];return true;}
	}
	return false;
}
int main(){
	freopen("1059.in","r",stdin);freopen("1059.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(e,0,sizeof(e));
		memset(pre,0,sizeof(pre));
		memset(now,0,sizeof(now));
		memset(to,0,sizeof(to));
		memset(from,0,sizeof(from));
		tail=0;flag=1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				scanf("%d",&tmp);
				if(tmp) add(i,j);
			}
		for(int i=1;i<=n;i++){
			memset(vis,0,sizeof(vis));
			if(!hungary(i)) {flag=0;break;}
		}
		printf(flag?"Yes\n":"No\n");
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter