题意

Link

Sol

给个其他题解都没给出过的方法:二分答案。

然后怎么 check 呢？

看 这个帖子。

（完）

解法：

抽象成图论问题：给定无向图，试给边加上方向使得每个点入度至少为 1。

二分答案，设二分到的答案是 $u$。

对于每一条边，若两个节点都大于 $u$，跳过之。

若两个节点仅一个大于 $u$，则指向小于 $u$ 的点，这个点成为 “自由点”。

然后连接所有剩下的边。

若最后存在没有自由点的树，那么不合法，否则合法。证明显然。

复杂度 $O(n\log m\alpha(n))$，其中 $m$ 是节点数，也就是最大的属性值。

Code

大概是因为我 sb 一样动态开并查集所以要开 O2，我也不知道为啥 O2 能从 1200ms+ 优化到 200ms。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
using namespace std;
const inline void readln(int&I){
	I=0;char C=getchar();
	while(!isdigit(C))C=getchar();
	while( isdigit(C))I=(I<<3)+(I<<1)+C-'0',C=getchar();
}
#define pii pair<int,int>
int n,c1,c2;
vector<pii >e;
bool operator<(pii pa,pii pb){
	if(pa.first==pb.first)return pa.second<pb.second;
	else return pa.first<pb.first;
}
int fi(vector<int>*f,int o){
	if((*f).at(o)==o)return o;
	else return (*f).at(o)=fi(f,(*f).at(o));
}
bool check(int u){
	vector<int>f(u+1),g(u+1);
	for(int i=1;i<=u;i++)
		f.at(i)=i,g.at(i)=0;
	for(int i=e.size()-1;i>=0;i--){
		if(e[i].first>u){
			if(e[i].second<=u)
				g.at(fi(&f,e[i].second))=1;
			continue;
		}
		int v1=fi(&f,e[i].first),v2=fi(&f,e[i].second);
		if(v1!=v2)f[v2]=v1,g[v1]|=g[v2];
		else g[v2]=1;
	}
	for(int i=1;i<=u;i++)
		if(f[i]==i && g[i]==0)return 0;
	return 1;
}
int main(){
	readln(n);
	for(int i=1;i<=n;i++)
		readln(c1),readln(c2),
		e.push_back(make_pair(max(c1,c2),min(c1,c2)));
	int l=0,r=n+1;
	while(l+1<r){//[l,r)
		int mid=((l+r)>>1);
		if(check(mid))l=mid;
		else r=mid;
	}
	printf("%d\n",l);
}

依旧给题解写题解

本篇题解主要解释两个问题：check函数的原理以及最终判断的依据

首先先解释为什么是给无向图赋方向。注意到如果你用了一个武器的一个属性就不能使用另一个属性，那么我们可以把这个过程建一个边，让这个边的终点为使用的属性。最后如果一个点入度不为$0$说明被使用过，所以最终给整个无向图赋方向之后如果有入读为$0$的点就不可行。

然后是为什么存在没有自由点的树就会使方案不合法。注意到一个树的叶子节点一定只有一条与之相连的边，那么如果要使方案合法，这条边一定指向叶子节点。但是这样一来叶子节点的父亲节点就没有入度了，需要父亲的父亲指向他，以此类推，根节点就没有入度了，肯定不合法。但是此时如果有一个自由点，它可以随意制造一个度，那么只需要让他做根节点即可，一定有方案合法。