【贪心+并查集】BZOJ1854 [Scoi2010]游戏

题面在这里

​

把武器看作边，属性值看作点

那么就是要把每个点与其邻边匹配

显然一个联通块有环则所有点都能匹配

否则只有1个点不能匹配，这里我们使属性值最大点不匹配

并查集合并联通块时维护每个点是否能找到匹配就好了

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=10005;
int n,fa[maxn];
bool vis[maxn];
inline int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=10000;i++) fa[i]=i;
	for (int i=1;i<=n;i++){
		int x,y;scanf("%d%d",&x,&y);
		if (getfa(x)==getfa(y)) vis[getfa(x)]=1;
		else vis[getfa(min(x,y))]=1,fa[getfa(min(x,y))]=getfa(max(x,y));
	}
	for (int i=1;i<=10001;i++)
	 if (!vis[i]) return printf("%d",i-1),0;
	return 0;
}