bzoj1854: [Scoi2010]游戏（二分图匹配）

题目传送门
好题！

解法：
想了一会儿如何限制选了一个另外一个不再选呢？
好像可以用二分图匹配诶。
每个装备的两个属性到这个装备有一个匹配关系。
然后就跑最大匹配就行了嘛。
从1开始，能匹配表示可以攻击到这个属性。
否则的话就不能再继续了。

真的卡时间边目录+时间戳

代码实现：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int x,y,next;
}a[2100000];int len,last[11100000];
void ins(int x,int y) {
    len++;
    a[len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}
int match[11100000],chw[1110000],t;
bool find_match(int x) {
    for(int k=last[x];k;k=a[k].next) {
        int y=a[k].y;
        if(chw[y]!=t) {
            chw[y]=t;
            if(match[y]==0||find_match(match[y])==true) {
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int n;scanf("%d",&n);
    len=0;memset(last,0,sizeof(last));
    int sum=0;
    for(int i=1;i<=n;i++) {
        int x,y;scanf("%d%d",&x,&y);
        ins(x,i);ins(y,i);sum=max(sum,max(x,y));
    }
    t=0;
    int ans=0;
    for(int i=1;i<=sum;i++) {
        t++;
        if(find_match(i)==true)
            ans++;
        else
            break;
    }
    printf("%d\n",ans);
    return 0;
}