BZOJ 1854: [Scoi2010]游戏 (并查集)

2017-10-25 · 2 min read · 并查集

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

Source

Day1

思路：

看到了二分图匹配的题解，但是感觉很错啊？

正确的做法是，将武器看成边，将每个武器的2种属性看成点。

使用某种属性，就要消耗一条边。

因此如果一个联通快是树形结构，k个点，k-1条边，因此有一个属性无法被使用。

由于要求是从1开始递增得攻击，因此显然使得属性最大的点不被使用是最优的。

如果一个联通块有环，那么所有的树型都可以被使用。

注意这个联通快有无环影响计数的思维，和codeforces # 440 div2 E. Points, Lines and Ready-made Titles 很像

/* ***********************************************
Author :111qqz
Created Time :2017年10月25日 星期三 17时00分25秒
File Name :1854.cpp
************************************************ */

 1#include <bits/stdc++.h>
 2#define PB push_back
 3#define fst first
 4#define sec second
 5#define lson l,m,rt<<1
 6#define rson m+1,r,rt<<1|1
 7#define ms(a,x) memset(a,x,sizeof(a))
 8typedef long long LL;
 9#define pi pair < int ,int >
10#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E6+7;
 7const int M=1E4+7;
 8int n;
 9bool ok[M];
10int f[M];

 1void init()
 2{
 3    ms(ok,false);
 4    for ( int i = 1 ; i < M ; i++) f[i] =  i;
 5}
 6int root ( int x)
 7{
 8    if (x!=f[x]) f[x] = root(f[x]);
 9    return f[x];
10}
11int main()
12{
13    #ifndef  ONLINE_JUDGE 
14    freopen("./in.txt","r",stdin);
15  #endif

 1    cin>>n;
 2    init();
 3    for ( int i = 1 ; i <= n ; i++)
 4    {
 5        int x,y;
 6        int fx,fy;
 7        scanf("%d %d",&x,&y);
 8        fx = root(x);
 9        fy = root(y);
10        if (fx!=fy)
11        {
12        if (fx<fy) swap(fx,fy);
13        ok[fy] = true;
14        f[fy] = fx;
15        }
16        else ok[fy] = true;
17    }
18    int ans;
19    for ( int i = 1 ; i < M ; i++)
20        if (!ok[i]) 
21        {
22        ans = i-1;
23        break;
24        }

    cout<<ans<<endl;

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}