「题解」苗条的生成树

给定一张连通图，求所有生成树中最大边权与最小边权差最小的，输出它们的差值……

一 题目

原题链接

描述

求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

输入

输入文件包含多组测试数据，每组测试数据如下： 第1行：2个整数n m （2 ≤ n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2），n表示顶点数，m表示边数。接下来m行，每行3个空格分开的整数a b w（1 ≤ w ≤ 10000） , 表示顶点a与顶点b之间有一条边，权值为w。

输出

对每组测试数据，如果图存在生成树，输出生成树的差值最小的；否则，输出-1。

---

二 题解

$n$不大，考虑暴力。

把边权升序排序，每次固定mst的第一条边，那么最后一条边也肯定固定了。（贪心原理：最后一条边越靠前差值越少）。枚举起始边，kruskal求最小生成树，维护最优解就好了。

复杂度大约是$O(q(m^2 +mlogm))$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int read(){
    int s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

const int CP=110;
const int CE=CP*CP;

const int INF=0x3f3f3f3f;

class fs{
  public:
      int from,to,dist;
      void init(int f,int t,int d)
      {from=f; to=t; dist=d;}
      bool operator < (const fs& e)const {return dist<e.dist;}
}E[CE];
int ecnt=0;
void add(int x,int y,int z){
    E[++ecnt].init(x,y,z);
}

//并查集
class ufs{ 
  public:
      int fa[CP];
      ufs() {for(int i=1;i<CP;i++) fa[i]=i;}
      void init() {for(int i=1;i<CP;i++) fa[i]=i;}
      int find(int u) {return fa[u]==u ? u : fa[u]=find(fa[u]);}
      bool exm(int x,int y) {return find(x)!=find(y);}
      void merge(int x,int y) {fa[find(x)]=find(y);}
}s;

//v define
int n,m;

//mst
int mst()
{
    sort(E+1,E+ecnt+1);
    
    int ans=INF;
    for(int st=1; st<=ecnt; st++) //枚举起始边
    {
        s.init();
        int cnt=0,lst=-1;        
        for(int k=st; k<=ecnt&&cnt!=n-1; k++) //kruskal
        {
            fs e=E[k];
            if(!s.exm(e.from,e.to)) continue;
            s.merge(e.from,e.to);
            lst=k; cnt++;
        }
        
        if(cnt != n-1) continue; //没能生成mst
        ans = min(ans, E[lst].dist-E[st].dist); //维护
    }
    
    return ans==INF ? -1 : ans;
}

int main()
{
    //freopen("out.out","w",stdout);

    n=read(); m=read();
    while(n)
    {
        ecnt = 0; //forward-star init
        while(m--) {
            int x=read(),y=read(),z=read();
            add(x,y,z);
        }
        
        printf("%d\n",mst());
        
        n=read(); m=read();
    }
    
    return 0;
}