P4234题解

· · 题解

以下是一些情（fei）节（hua）

Two\ Month\ Later

After\ test

Anonymous31416:

今天的最小差值生成树好简单啊！就是板子题！我秒切了！

Two\ minutes\ later

Anonymous31416:

诶，洛谷上怎么也有这道题？

After\ dinner

Anonymous31416:

What!我只得了30分！

Another\ fifteen\ minutes

Anonymous31416:

我玄学优化拿了75分！

Last\ Week

2020-12-11\ 9\ p.m.

Anonymous31416:

我最小差值生成树A了！，不用LCT！！！

EXODUS:Orz!tql!

Now

EXODUS:我也A了！

于是我就来发题解了

以下是正文部分

首先，看到这一道题，第一个想法就是暴力。也就是说，枚举选取的最小的边，开始跑Kruskal。于是就有了75分。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define il inline
using namespace std;

int m,m0,n;
struct Edge{
    int u,v,w;
}e[285714];
int fa[142857];
int eu,ev;
int ans=0x3f3f3f3f,cnt;

int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}

il bool cmp(Edge x,Edge y){
    return x.w<y.w;
}

il int find(int x){
    while(x!=fa[x]){
        x=fa[x]=fa[fa[x]];
    }
    return x;
}

il void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

il void kruskal(){
    cnt=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        cnt=0;
        init();
        for(int j=i;j<=m;j++){
            eu=find(e[j].u);
            ev=find(e[j].v);
            if(eu==ev){
                continue;
            }
            fa[eu]=ev;
            if(ans<e[j].w-e[i].w){
                break;
            }
            if(++cnt==n-1){
                ans=min(ans,e[j].w-e[i].w); 
                break;
            }
        }
    }
}

int main(){
    //freopen("mdt.in","r",stdin);
    //freopen("mdt.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u,v,w;
        u=read(),v=read(),w=read();
        if(u==v){
            continue;
        }else{
            e[i].u=u;
            e[i].v=v;
            e[i].w=w;
        }
    }
    kruskal();
    cout<<ans;
    return 0;
}

但是问题来了，然后呢？

很明显，这里出现了一些不合法的状态。即在此时枚举的i的编号< n-1时，已经不会生成树了，更不会出现最小生成树了。所以，这些状态可以减掉。 所以说就可以出现93分代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#define il inline
using namespace std;

map<int,bool>f;
int m,m0,n;
struct Edge{
    int u,v,w;
}e[285714];
int fa[142857];
int flag=1;
int eu,ev;
int ans=0x3f3f3f3f,cnt;

int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}

il bool cmp(Edge x,Edge y){
    return x.w<y.w;
}

il int find(int x){
    while(x!=fa[x]){
        x=fa[x]=fa[fa[x]];
    }
    return x;
}

il void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

il void kruskal(){
    cnt=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        cnt=0;
        init();
        for(int j=i;j<=m;j++){
            eu=find(e[j].u);
            ev=find(e[j].v);
            if(eu==ev){
                continue;
            }
            fa[eu]=ev;
            if(++cnt==n-1){
                ans=min(ans,e[j].w-e[i].w); 
                break;
            }
        }
        if(cnt<n-1){
            break;
        }
    }
}

int main(){
    //freopen("mdt.in","r",stdin);
    //freopen("mdt.out","w",stdout);
    n=read(),m0=read();
    for(int i=1;i<=m0;i++){
        int u,v,w;
        u=read(),v=read(),w=read();
        if(f[w]==0&&i!=1){
            flag=0;
        }
        if(u==v){
            continue;
        }else{
            e[m].u=u;
            e[m].v=v;
            e[m].w=w;
            m++;
        }
    }
    if(flag){
        cout<<0;
        return 0;
    }
    kruskal();
    cout<<ans;
    return 0;
}

也就是说，这一道题93分的分数都可以不用LCT实现。那么接下来的问题就是，剩下的7分怎么办？

接下来，我就开始了玄学路线。

首先，本着优化的目的，我在我的代码中加入了

    if(ans==0){
        break;
   }

结果，结果就A了？？！！ AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define il inline
using namespace std;
int m,n;
struct Edge{
    int u,v,w;
}e[285714];
int fa[142857];
int flag=1;
int eu,ev;
int ans=0x3f3f3f3f,cnt;

int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}

il bool cmp(Edge x,Edge y){
    return x.w<y.w;
}

il int find(int x){
    while(x!=fa[x]){
        x=fa[x]=fa[fa[x]];
    }
    return x;
}

il void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

il void kruskal(){
    cnt=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        cnt=0;
        init();
        for(int j=i;j<=m;j++){
            eu=find(e[j].u);
            ev=find(e[j].v);
            if(eu==ev){
                continue;
            }
            fa[eu]=ev;
            if(++cnt==n-1){
                ans=min(ans,e[j].w-e[i].w); 
                break;
            }
        }
        if(cnt<n-1||ans==0){
            break;
        }
    }
}

int main(){
    //freopen("mdt.in","r",stdin);
    //freopen("mdt.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u,v,w;
        u=read(),v=read(),w=read();
        if(u==v){
            continue;
        }else{
            e[i].u=u;
            e[i].v=v;
            e[i].w=w;
        }
    }
    kruskal();
    cout<<ans;
    return 0;
}

总的来说，这一道题的前93分并不是紫题，只能算是难度偏高的绿题。只有最后一个点需要使用LCT，但一旦加入了一个看似不必要的优化，就能A掉此题。

最后，还是希望大家可以学习LCT后并解决此题，因为毕竟考场上并不是每一道题都可以这样优化后通过的。

求各位给个赞呗（学LCT去了，逃\~~）

The\ end