BZOJ1854: [Scoi2010]游戏

1854: [Scoi2010]游戏

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 5931 Solved: 2397
[Submit][Status][Discuss]

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

HINT

【数据范围】
对于30%的数据，保证N < =1000
对于100%的数据，保证N < =1000000

题解

首先我们把每个武器看做一条边，把权值看做点

对于每条边最多只能选中其一个端点

那么我们想象，如果有n个点形成了一棵树，那么我们能选中其中几个点？

答案是n - 1个

我们把树上每条边看做儿子向的链接，那么显然除了根节点都会有一条独属于自己的链接

但如果有一个环就不一样了

首先除了环外的部分看做树，树的根节点向环连边可以看做是属于根节点的边，而一个n元环有n条边刚好可以均匀分配，所以存在环的图一定可以都取到

我们要找最长连续可取，我们只需标上哪些点可取，从1扫一遍就好了

对于有环的图全都可取，对于树我们标树中最大的那个不可取

怎么实现呢？

用并查集。

对于边(a,b)，我们找到a,b所在联通块根节点fa,fb

若fa != fb，将较小者的父亲记为较大者，标较小者为true，这样保证如果成树一定是最大的那个没有标上，若根本身就已经是true，说明已经成环，那么两者都标上true

如果fa == fb，说明现在成环，都标true

最后扫一遍vis就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 10005,maxm = 1000005,INF = 1000000000;
inline int read(){
	int out = 0,flag = 1;char c = getchar();
	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
	while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
	return out * flag;
}
int N,pre[maxn],n = 10000;
bool vis[maxn];
inline int find(int u) {return u == pre[u] ? u : pre[u] = find(pre[u]);}
int main()
{
	int a,b,fa,fb;
	N = read();
	REP(i,n) pre[i] = i;
	REP(i,N){
		a = read(); b = read();
		fa = find(a); fb = find(b);
		if (fa > fb) swap(fa,fb);
		if (fa != fb) {
			pre[fa] = fb;
			if (vis[fa]) vis[fb] = true;
			vis[fa] = true;
		}else vis[fb] = true;
	}
	REP(i,N + 1) if (!vis[i]) {printf("%d
",i - 1); break;}
	return 0;
}