【题意】

给出一个\(n(n<=100)\)个节点的的图，求最大边减最小边尽量小的生成树。

【算法】

\(Kruskal\)

【分析】

首先把边按边权从小到大进行排序。对于一个连续的边集区间\([L,R]\)，如果这些边使得\(n\)个点全部联通，则一定存在一个苗条度不超过\(W[R]-W[L]\)的生成树（其中\(W[i]\)表示排序后第\(i\)条边的权值）。

从小到大枚举\(L\)，对于每个\(L\)，从小到大枚举\(R\)，同时用并查集将新进入\([L,R]\)的边两端的点合并成一个集合，与\(Kruskal\)算法一样。当所有的点都联通是停止枚举\(R\)，换下一个\(L\)(并且把\(R\)重置为\(L\))，继续枚举。

【代码】

#include
    
     using namespace std;const int MAXN=100+10;const int MAXM=10000+10;int n,m;int fa[MAXN];int maxn,ans=0x3f3f3f3f;struct Node{    int u,v,w;}edge[MAXM];inline int read(){    int tot=0;    char c=getchar();    while(c<'0'||c>'9')        c=getchar();    while(c>='0'&&c<='9')    {        tot=tot*10+c-'0';        c=getchar();     }    return tot;}inline bool cmp(Node x,Node y){    return x.w
    

刘汝佳大法好！