[SCOI2010 第一试 游戏]二分图匹配 or 并差集

【题目】

Description

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备 时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。
游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生 伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个 属性值为3的装备攻击boss……以此类推。
现在lxhgww想知道他最多能连续攻击boss多少次?

Input

输入的第一行是一个整数N,表示lxhgww拥有N种装备
接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值

Output

输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。

Sample Input

3
1 2
3 2
4 5

Sample Output

2

Hint

对于30%的数据,保证N<=1000
对于100%的数据,保证N<=1000000 【算法分析】
做法1:
这是通法~
我们把那个10000个数字放在二分图的左边,然后把武器放在二分图的右边。
对于一个武器,连左边两个对应的点。
然后从左边的点1开始一直像正常的匹配那样搞下去,直到某一个地方,找不到增广路,证明前i个点不能被同时满足了。那么输出i-1即可。

做法2:
这个我觉得并不容易想到。
把那10000个点看成点。
然后武器看成无向边。
(1)对于一个联通块,假如不含环(就是一棵树),那么必定可以满足其中任意的p-1个点。
(2)对于一个联通块,假如含环,那么必定全部的p个点都能满足。
如此用并差集维护即可。
对(1)容易用数学归纳法证明。
对(2),可以通过(1)来证明。
【其他】
实际测试表明,匹配和并差集的速度差不多。
注:并差集用的IO外挂,所以速度会快很多,实际上去掉以后速度是差不多的。
【CODE——匹配】
#include #include #include const int N=1000005;
struct gtp{int y,next;}g[N*2];
int n,e;
int a[N*2][2],v[N*2],ls[10005],link[N*2];

inline void addedge(int x,int y){
e++;
g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

bool find(int p,int kk){
int q;
for (int t=ls[p];t;t=g[t].next)
if (v[g[t].y]!=kk){
v[g[t].y]=kk;
q=link[g[t].y];
link[g[t].y]=p;
if (!q || find(q,kk)) return true;
link[g[t].y]=q;
}
return false;
}

void solve(){
e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++){
addedge(a[i][0],i);
addedge(a[i][1],i);
}
for (int i=1;i<=10001;i++){
if (!find(i,i)){
printf("%dn",i-1);
return;
}
}
}

int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i][0],&a[i][1]);
solve();
}

【CODE——并差集】
#include #include #include const int N=10005;
int n;
int f[N],v[N];
char ch;

int gf(int p){
if (f[p]==p) return p;
return f[p]=gf(f[p]);
}

inline void Read(int &x){
x=0;
ch=getchar();
while (ch==’ ‘ || ch==’n’) ch=getchar();
while (ch!=’ ‘ && ch!=’n’){
x=x*10+ch-‘0’;
ch=getchar();
}
}

int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int x,y,i,tmp;
for (i=1;i<=N;i++){
f[i]=i;
v[i]=0;
}
Read(n);
for (i=1;i<=n;i++){
Read(x); Read(y);
if (gf(x)!=gf(y)){
if (f[x]>f[y]){tmp=x; x=y; y=tmp;}
v[f[y]]|=v[f[x]];
f[f[x]]=f[y];
}else v[f[x]]=1;
}
for (i=1;i if (f[i]==i && !v[i]){
printf("%dn",i-1);
break;
}
}

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注