题解:
解法一:建立图论模型,发现只要联通块中有环则这个联通块中的值都可以被攻击到
如果是树,则只能攻击size-1个
解法二:二分图匹配,二分答案,看看是否能攻击到mid
#include
#include
#include
using namespace std;
const int u=10000;
int n;
int father[u+1];
int isinc[u+1];
int siz[u+1];
int Getf(int x){
if(father[x]==x)return x;
return father[x]=Getf(father[x]);
}
void Unionn(int x,int y){
int fx=Getf(x);
int fy=Getf(y);
if(fx!=fy){
father[fx]=fy;
siz[fy]+=siz[fx];
isinc[fy]=isinc[fy]|isinc[fx];
}
}
int main(){
for(int i=1;i<=u;++i)father[i]=i;
for(int i=1;i<=u;++i)siz[i]=1;
scanf("%d",&n);
while(n--){
int x,y;
scanf("%d%d",&x,&y);
if(Getf(x)==Getf(y)){
isinc[Getf(x)]=1;
}else{
Unionn(x,y);
}
}
for(int i=1;i<=u;++i){
int f=Getf(i);
if(isinc\[f\])continue;
if(siz\[f\]==1){
printf("%d\\n",i-1);
return 0;
}
--siz\[f\];
}
printf("%d\\n",u);
return 0;
复制
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章