[题意]
给出一个 \(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<bits/stdc++.h>
- 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<y.w;
- }
- inline int find(int k)// 并查集
- {
- if(fa[k]==k)return k;
- else return fa[k]=find(fa[k]);
- }
- inline bool kruskal(int k)// 判断是否能形成生成树
- {
- maxn=0;
- int tot=0;
- for(int i=1;i<=n;i++)
- fa[i]=i;
- for(int i=k;i<=m;i++)
- {
- if(fa[find(edge[i].u)]!=fa[find(edge[i].v)])
- {
- maxn=edge[i].w;
- fa[find(edge[i].u)]=fa[find(edge[i].v)];
- tot++;
- }
- if(tot==n-1)return 1;// 如果所有点都联通, 则返回 true
- }
- return 0;// 否则返回 false
- }
- int main()
- {
- while(1)
- {
- ans=0x3f3f3f3f;
- n=read();m=read();
- if(!n&&!m)break;
- for(int i=1;i<=m;i++)
- {
- edge[i].u=read();
- edge[i].v=read();
- edge[i].w=read();
- }
- sort(edge+1,edge+1+m,cmp);// 给边进行从小到大排序
- for(int i=1;i<=m;i++)// 枚举 L
- {
- if(kruskal(i))
- {
- ans=min(ans,maxn-edge[i].w);// 更新最小值
- }
- }
- if(ans!=0x3f3f3f3f)cout<<ans<<endl;
- else cout<<-1<<endl;// 特判
- }
- return 0;
- }
刘汝佳大法好!
来源: http://www.bubuko.com/infodetail-3111513.html