BZOJ [Scoi2010]游戏
阅读原文时间:2023年07月10日阅读:2

题解:

解法一:建立图论模型,发现只要联通块中有环则这个联通块中的值都可以被攻击到

如果是树,则只能攻击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;  复制

}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章