bzoj1854 [Scoi2010]游戏

1854: [Scoi2010]游戏

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 5354 Solved: 2151
[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

Source

Day1

分析：一道比较裸的二分图匹配，把属性放左边，装备放右边，第i个装备有属性j,就从j向i连一条有向边，然后从小到大枚举属性值，看能不能匹配上，如果不行输出i-1即可.

不过还是TLE了，算法基本上是不能优化了，比较耗时间的是vis数组的memset,每次要操作100w个元素，最坏情况要操作10000次，直接T飞了，正确的做法是时间戳，相当于dfs_clock的东西，if(vis[i])就相当于if(vis[i] == t),相当于把1变成了t,每次memset操作只需要t++即可.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>

using namespace std;

const int inf = 0x7ffffff;

int n,vis[1000010],to[2000010],nextt[2000010],tot,head[1000010],pipei[1000010],clockk;

void add(int x, int y)
{
    to[tot] = y;
    nextt[tot] = head[x];
    head[x] = tot++;
}

bool find(int x)
{
    for (int i = head[x]; i + 1; i = nextt[i])
    {
        int v = to[i];
        if (vis[v] != clockk)
        {
            vis[v] = clockk;
            if (!pipei[v] || find(pipei[v]))
            {
                pipei[v] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    bool flag = false;
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, i);
        add(b, i);
    }
    int i;
    for (i = 1; i <= 10001; i++)
    {
        ++clockk;
        if (!find(i))
        {
            printf("%d
", i - 1);
            flag = 1;
            break;
        }
    }
    if (!flag)
        printf("%d
", i);

    return 0;
}