题意:
lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。
游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次?
题解:
看了看提交AC的一些代码,一看代码好短,但是想了想这些代码好像有点问题,好像是测试点不够强,所以AC了。
然后去看了看大神们的题解,原来是用二分图,这题把图建好就差不多是一个模板题吧。
就注意以下如何建图就可以了。

    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        add(x,i);
        add(y,i);
    }

代码:

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstdio>
#include <string.h>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<cmath>
#include <math.h>
#include<algorithm>

//#define int long long
using namespace std;
const int maxn = 1e6+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

struct node{
    int next,to;
}edge[maxn*2];
int head[maxn];
int match[maxn];
bool visited[maxn];
int cnt=0;
void add(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
bool dfs(int x){
    for(int i=head[x];~i;i=edge[i].next){
        int v=edge[i].to;
        if(!visited[v]){
            visited[v]=true;
            if(!match[v]||dfs(match[v])){
                match[v]=x;
                return true;
            }
        }
    }
    return false;
}

signed main()
{
    int n;
    memset(head,-1,sizeof head);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        add(x,i);
        add(y,i);
    }
    for(int i=1;i<maxn;i++){
        memset(visited,0,sizeof visited);
        if(!dfs(i)){
            cout<<i-1<<endl;
            return 0;
        }
    }
    return 0;
}