DQS DQS

[BZOJ1854][Scoi2010]游戏 并查集||匈牙利

in 算法,并查集,图论,匈牙利算法&&KM算法,数据结构read (60) 文章转载请注明来源!

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

Source

Day1


第一想法是贪心:点对内有序,再对所有点对排序。从前到后能选则选。
hack:当x相同时,y不同,此时应该选择一个,其他的点对属性为y。但这个算法的做法是全部舍弃。

正解:

算法一:

二分图匹配。

新建10000个属性节点,与对应的装备连边。枚举属性做二分图匹配,有一个配不上则输出答案。

算法二:

精妙的并查集。

若一个装备为边,即两个属性之间连一条边的话,会形成很多联通块。

若联通块有环,则属性可以全选。
若联通块无环(即是树),则必须舍弃一个点。当然我们舍弃最大的那个点。

于是对装备扫一遍合并就好了。

注意代码写法:第一个遇到的无环联通块就应该停止,此时答案是它前面所有数字都选。
若不存在这种联通块,则说明所有点都在有环的联通块内,即可以全选。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a < '0' || a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int n;
int fa[SZ];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
bool is[SZ];

int main()
{
    n = read();
    for(int i = 1;i <= 10000;i ++) fa[i] = i;
    for(int i = 1;i <= n;i ++)
    {
        int a = read(),b = read();
        int x = find(a),y = find(b);
        if(x == y) is[x] = 1;
        else
        {
            if(x > y) swap(x,y);
            is[y] |= is[x];
            fa[x] = y;
        }
    }
    for(int i = 1;i <= 10000;i ++)
    {
        int x = find(i);
        if(is[x]) continue;
        if(x == i) { printf("%d\n",i - 1); return 0; }
    }
    printf("%d",10000);
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆