洛谷 P1640 [SCOI2010]连续攻击游戏（二分图匹配）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000010
using namespace std;
int n,vis[MAXN],net[MAXN];
int head[10010],nxt[MAXN*2],to[MAXN*2],tot,tim;

void read(int &X){
    int x=0,f=1;char c=getchar();
    while(c<‘0‘||c>‘9‘) {if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘) {x=x*10+c-‘0‘;c=getchar();}
    X=x*f;
}

void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}

bool match(int u){
    for(int i=head[u];i;i=nxt[i])
        if(vis[to[i]]<tim){
            vis[to[i]]=tim;
            if(!net[to[i]] || match(net[to[i]])){
                net[to[i]]=u;
                return true;
            }
        }
    return false;
}

int main(){
    read(n);
    for(int i=1,a,b;i<=n;i++){read(a);read(b);add(a,i);add(b,i);}
    for(int i=1;i<=10001;i++){
        tim++;               //用时间戳代替初始化vis数组，加快效率 
        if(!match(i)){
            printf("%d\n",i-1);
            return 0;
        }
    }    
    return 0;
}