洛谷 P1640 BZOJ 1854 [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最多能連續攻擊的次數。

輸入輸出樣例

輸入樣例#1：

3
1 2
3 2
4 5
      

輸出樣例#1：

2      

說明

Limitation

對于30%的資料，保證N < =1000

對于100%的資料，保證N < =1000000

來源：SCOI 2010

解題思路

　　先手算一波，發現自己手算的過程就是匈牙利算法啊，于是套上闆子即可。

　　這裡有個vis數組，1e6太大了，不能每次都清零vis，否則會逾時的。這裡引入一個時間标簽，用時間戳cnt替換掉true，就不用每次都清零vis了，用vis[u]==cnt替換vis[u]==true即可

源代碼

#include<vector>
#include<cstdio>
using namespace std;
int n;
struct men{
    vector<int> t;//備用的tyre#滑稽
    int lover;
}man[1000010];
int woman[1000010]={0};
int vis[1000010]={0};
int cnt=0;//避免每次清零vis
bool dfs(int u)
{
    int sz=man[u].t.size();
    for(int i=0;i<sz;i++)
    {
        int w=man[u].t[i];
        if(vis[w]!=cnt)
        {
            vis[w]=cnt;
            if(!woman[w]||dfs(woman[w]))
            {
                woman[w]=u;
                man[u].lover=w;
                return 1;
            }
        }
    }
    return 0;
}


int main()
{
    scanf("%d",&n);
    for(int i=1,u,v;i<=n;i++)
    {
        scanf("%d%d",&u,&v);
        man[u].t.push_back(i);
        man[v].t.push_back(i);
        man[i].lover=0;
    }
    for(int i=1;i<=n;i++)
    {
        cnt++;
        if(!dfs(i))
        {
            printf("%d\n",i-1);
            return 0;
        }
    }
    printf("%d",n);
    return 0;
}