lp1640 SCOI2010 连续攻击游戏

一般地，对于兼具可行性和唯一性的问题，我们考虑二分图匹配。
对于这一题来说，我们考虑拆点。
值得一提的是，这里的拆点并不是将一个点的两个属性拆开来，而是将一个点的属性和编号拆开来。然后跑匈牙利。
如果可以匹配，那就继续匹配；如果不能匹配，那就说明这个属性无论如何也取不到；或者取到它需要付出「前面有某个属性无法取到」的代价，那么就是没有答案了。

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[2000005];
int h[10005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}

int n;
int vis[1000005],dep;
int usd[1000005];

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a,&b);
		add(a,i),add(b,i);
	}
	int ans=0;
	dep=0;
	for(int i=1;i<=n;++i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}