[SCOI2010]游戏

分析

二分图匹配，对于第 i 个装备两个属性 x 和 y ，建立两条边，x -> i ，y -> i 。

然后利用匈牙利算法，从 1 开始往后匹配，当匹配不成功的时候就结束。

正常的匈牙利算法可能会因为要 memset 很多次可能超时，虽然没有超时，可能数据水或者我理
解有问题之类的。

然后可以利用时间戳来避免 memset 的操作。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 10110;
const int M = 1e9+7;
int n,now;

int match[maxn];

bool vis[maxn];

vector<int> v[maxn];

bool find(int x)
{
    for(auto y : v[x])
    {
        if(vis[y] == now)
        {
            vis[y] = now;
            if(match[y] == 0 || find(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i = 1,x,y; i <= n; i++) 
    {
        cin>>x>>y;
        v[x].push_back(i);
        v[y].push_back(i);
    }
    now = 1;
    while(find(now)) now++;
    cout<<now-1<<endl;
    return 0;
}