[SCOI2010]游戏

题意：
你有n件装备，每件装备有两个属性，每件装备只能用一次，你打boss时属性只能从1开始连续用装备攻击，求你的最大攻击次数。

思路：
二分图匹配问题，属性与物品编号连边，从1开始匹配，用匈牙利算法，冲突时进行改变。

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=998244353;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int ma[1000005], t[1000005][2], mb[1000005];
vector<int> g[1000005];

int dfs(int k)
{
    for(int i=0; i<g[k].size(); i++)
    {
        if(!ma[g[k][i]])
        {
            ma[g[k][i]]=1;
            return 1;
        }
    }
    for(int i=0; i<g[k].size(); i++)
    {
        if(!mb[g[k][i]])
        {
            mb[g[k][i]]=1;
            if(t[g[k][i]][0]==k&&dfs(t[g[k][i]][1]))
            {
                ma[g[k][i]]=1;
                return 1;
            }
            else if(t[g[k][i]][1]==k&&dfs(t[g[k][i]][0]))
            {
                ma[g[k][i]]=1;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(i);
        g[v].push_back(i);
        t[i][0]=u;
        t[i][1]=v;
    }
    int i=1;
    for(; i<=n+1; i++)
    {
        if(dfs(i))
        {
            ;
        }
        else
        {
            break;
        }
    }
    cout << i-1 << endl;
    return 0;
}