题解 P6004 【[USACO20JAN]Wormhole Sort S】

· · 题解

[USACO20JAN]Wormhole Sort S

显然就是一个模板题了。

题意就是说有n个虫洞，在两个地方传送，现在问你让所有的奶牛都到自己的地方所穿过的虫洞宽度最小的最大值是多少。

抓住关键信息：

1.一个虫洞如果确定了要经过，那么就可以无限经过这个虫洞

2.当确定一个虫洞要经过之后，宽度比他大的虫洞都可以经过

每条边都可以无限次穿过，并且要判断两个地方是否有联通性，显然就对应了一个数据结构——并查集

所以可以得到一个暴力代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100001],a[100001];
bool ff;
inline void read(int &x){   //复古Pascal版快读
    x=0;int f=1;char s=getchar();
    for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=(x<<3)+(x<<1)+s-48;
    x*=f;
}
struct hzy{
    int x,y,z;   //x，y表示相连接的两点，z表示宽度
}cow[100005];
int zuxian(int k){//查找祖先，可以简化为return f[k]==k?k:f[k]=zuxian(f[k]);
    if(f[k]==k){
        return k;
    }
    else{
        return f[k]=zuxian(f[k]);
    }
}
bool mycmp(hzy a,hzy b){
    return a.z>b.z;//先用宽度大的边
}
int main(){
    read(n);
    read(m);
    ff=0;
    for(int i=1;i<=n;i++){
        f[i]=i;
        read(a[i]);
        if(a[i]!=i){
            ff=1;
        }
    }
    if(ff==0){//如果不需要移动
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<=m;i++){//无需解释的读入
        read(cow[i].x);
        read(cow[i].y);
        read(cow[i].z);
    }
    sort(cow+1,cow+m+1,mycmp);
    for(int i=1;i<=m;i++){//并查集过程
        int x1=zuxian(cow[i].x);
        int x2=zuxian(cow[i].y);
        if(x1!=x2){
            f[x1]=f[x2];
        }
        ff=0;
        for(int j=1;j<=n;j++){//判断每个奶牛是否可以到自己的位置上
            if(zuxian(a[j])!=zuxian(j)){
                ff=1;
            }
        }
        if(ff==0){//如果都满足要求，直接输出
            cout<<cow[i].z<<endl;
            return 0;
        }
    }
    return 0;
}

然而。。。悲惨TLE。

毕竟时间复杂度是O(nm+mlogm)，考虑怎么优化

还可以得到一个性质：当一个点已经满足要求时，那么在加边还是满足要求，那么就不需要每次都判断一下，只需要统计一下即可，时间复杂度O(n+m+mlogm)

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100001],a[100001];
bool ff;
inline void read(int &x){
    x=0;int f=1;char s=getchar();
    for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=(x<<3)+(x<<1)+s-48;
    x*=f;
}
struct hzy{
    int x,y,z;
}cow[100005];
int zuxian(int k){
    if(f[k]==k){
        return k;
    }
    else{
        return f[k]=zuxian(f[k]);
    }
}
bool mycmp(hzy a,hzy b){
    return a.z>b.z;
}
int main(){
    read(n);
    read(m);
    ff=0;
    for(int i=1;i<=n;i++){
        f[i]=i;
        read(a[i]);
        if(a[i]!=i){
            ff=1;
        }
    }
    if(ff==0){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<=m;i++){
        read(cow[i].x);
        read(cow[i].y);
        read(cow[i].z);
    }
    sort(cow+1,cow+m+1,mycmp);
   int j=1;
    for(int i=1;i<=m;i++){
        int x1=zuxian(cow[i].x);
        int x2=zuxian(cow[i].y);
        if(x1!=x2){
            f[x1]=f[x2];
        }
        while(zuxian(j)==zuxian(a[j])){//唯一的不同在这里，看似while在for里面，其实是并列关系
            j++;
        }
        if(j>n){
            cout<<cow[i].z<<endl;
            return 0;
        }
    }
    return 0;
}

求管理大大通过，蒟蒻求赞