洛谷 P1640 [SCOI2010] 连续攻击游戏题解
注意到值域是 \([1,10000]\)，所以我们可以将武器攻击值放在左部，武器编号放在右部，那么就是一个二分图。那么答案就是从 \(1\) 开始枚举左部的点直至无法匹配为止。时间复杂度 \(O(Vn)\)，其中 \(V\) 是值域。但是由于一次修改最多修改 \(O(V)\) 个点的匹配，所以根本跑不满。
bool dfs(int now) {
for(auto v:G[now]) {
if(!vis[v]) {
vis[v]=1;
if(!to[v]||dfs(to[v])) return to[v]=now,1;
}
}
return 0;
}
signed main() {
in1(n);
For(i,1,n) {
int x,y;
in2(x,y);
add(x,i);
add(y,i);
}
int ans=0;
For(i,1,10000) {
m0(vis);
if(!dfs(i)) {
cout<<i-1;
return 0;
}
}
cout<<10000<<'\n';
}