BZOJ 1854: [Scoi2010]游戏

starli posted @ 2016年2月14日 19:18 in 二分图 , 172 阅读

二分图匹配问题

属性为一边,装备为另一边,每一个装备连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;
}

登录 *


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