BZOJ 1854: [Scoi2010]游戏

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

二分图匹配问题

属性为一边,装备为另一边,每一个装备连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;
}
Avatar_small
deep cleaning servic 说:
2019年9月15日 14:59

Servicing Services LLC can be a professional washing services inside Dubai. You can expect efficient and also perfectly costed cleaning program for villas, apartments and also buildings(Domestic/Residential) along with Office/ Professional spaces. You can even avail our own maid program in Dubai. Super trustworthy and trained in your free time maid about hour schedule or regular maid program is what we need to offer. Our strong cleaning companies for home-based and places of work are being among the most in-demand program since recent years. Had a celebration last night time? Leave the particular after get together cleaning about us and you also sit again relaxed.


登录 *


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