BZOJ 1854: [Scoi2010]游戏

二分图匹配问题

属性为一边,装备为另一边,每一个装备连2条边,枚举属性进行匈牙利算法 

但是这题有一个优化 因为flag每次都重置的话需要花很长时间,我们采用一个时间戳,每次进行匹配的时候T++,flag就用T来代替

注意不能直接输出T-1,因为如果匹配完全的话,就是输出T了

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1000010;
int to[N*2],pre[N*2],now[N],from[N],flag[N],T,tail,n,a,b;
void add(int u,int v){to[++tail]=v;pre[tail]=now[u];now[u]=tail;}
bool hungary(int a){
	for(int i=now[a];i;i=pre[i]) if(flag[to[i]]!=T){
		flag[to[i]]=T;
		if(!from[to[i]] || hungary(from[to[i]])){from[to[i]]=a;return true;}
	}
	return false;
}
void read(int &x){
	char c;
	while((c=getchar())<'0'||c>'9');x=c-'0';
	while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1854.in","r",stdin);freopen("1854.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(a),read(b),add(a,i),add(b,i);
	for(int i=1;i<=10000;i++){
		T++;
		if(!hungary(i)) {T--;break;}
	}
	printf("%d",T);
	return 0;
}

BZOJ 1191: [HNOI2006]超级英雄Hero

二分图匹配 从第一个开始找匹配 找到第一个无法匹配的break并输出

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1010;
int help[N][2],from[N],n,m,ans,flag[N];
bool hungary(int x){
	for(int i=0;i<=1;i++) {
		int tmp=help[x][i];
		if(flag[tmp]) continue;else flag[tmp]=1;
		if(!from[tmp] || hungary(from[tmp])){from[tmp]=x;return true;}
	}
	return false;
}
int main(){
	//freopen("1191.in","r",stdin);freopen("1191.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&help[i][0],&help[i][1]);
	for(int i=1;i<=m;i++){
		memset(flag,0,sizeof(flag));
		if(hungary(i)) ans++;else break;
	}
	printf("%d",ans);
	return 0;
}

BZOJ 1059 [ZJOI2007]矩阵游戏

类似于这道题的题似乎以前多面体在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;
}