【二分图匹配】【SCOI2010】游戏

62 阅读 0 评论 41 点赞

我是靠谱客的博主危机酸奶，最近开发中收集的这篇文章主要介绍【二分图匹配】【SCOI2010】游戏，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题目描述】
lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。
游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。
现在lxhgww想知道他最多能连续攻击boss多少次？
【输入】
输入的第一行是一个整数N，表示lxhgww拥有N种装备
接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值
【输出】
输出一行，包括1个数字，表示lxhgww最多能连续攻击的次数。
【样例输入】
3
1 2
3 2
4 5
【样例输出】
2
【数据范围】
    对于30%的数据，保证N<=1000
    对于100%的数据，保证N<=1000000

这是一道较裸的二分图最大匹配，不作多说。

Accode：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <bitset>

using std::bitset;

const char fi[] = "game.in";
const char fo[] = "game.out";
const int maxN = 1000010;
const int MAX = 0x3f3f3f3f;
const int MIN = ~MAX;

struct Edge
{
    int u, v;
    Edge *next;
};
Edge *edge[maxN];
bitset <maxN> marked;
int a[maxN], b[maxN];
int Link[maxN];
int n, m;

void init_file()
{
	freopen(fi, "r", stdin);
	freopen(fo, "w", stdout);
	return;
}

inline void insert(int u, int v)
{
    Edge *p = new Edge;
    p -> u = u;
    p -> v = v;
    p -> next = edge[u];
    edge[u] = p;
    return;
}

void readdata()
{
    scanf("%d", &m);
    for (int j = 1; j < m + 1; ++j)
    {
        scanf("%d%d", a + j, b + j);
        n = std::max(n, a[j]);
        n = std::max(n, b[j]);
        insert(a[j], j);
        insert(b[j], j);
    }
	return;
}

bool Find(int u)
{
    for (Edge *p = edge[u]; p; p = p -> next)
    {
        int v = p -> v;
        if (!marked.test(v))
        {
            marked.set(v);
            if (!Link[v] || Find(Link[v]))
            {
                Link[v] = u;
                return true;
            }
        }
    }
    return false;
}

void work()
{
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        marked.reset();
        if (Find(i)) ++ans;
        else break;
    }
    printf("%d", ans);
	return;
}

int main()
{
	init_file();
	readdata();
	work();
	return 0;
}