點選打開連結 模闆題
Kruskal算法是求最小生成樹的較為高效的算法，首先根據邊的權值從小到大排序，n個頂點的最小生成樹需要n-1條邊，周遊排序後的邊，若兩個頂點不連通則加入這條邊（可用反證法證明），知道加入了n-1條邊，用并查集将聯通的頂點放在一個集合裡，并查集把集合按樹的形式放在一個集合裡。
題意：n個頂點，m條邊，每條邊有權值，求最小生成樹。
分析：先判斷m條邊能否是n個頂點聯通，能則存在最小生成樹，否則不存在輸出-1.
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int,int> pa;
const int maxn=105;
int parent[maxn];
struct Edge
{
int a,b,w;
bool operator<(const Edge& u)const
{
return w<u.w;
}
}edge[5000];
int n,m;
int find(int x)
{
return parent[x]==x?x:parent[x]=find(parent[x]);
}
bool un(int i,int j)
{
int x=find(i);
int y=find(j);
if(x==y)
return false;
parent[x]=y;
return true;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
break;
for(int i=1;i<=n;i++)
parent[i]=i;
int e=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&edge[e].a,&edge[e].b,&edge[e].w);
un(edge[e].a,edge[e].b);
e++;
}
int d=0;
for(int i=1;i<=n;i++)
{
if(parent[i]==i)
d++;
}
if(d>1)
{
printf("-1\n");
continue;
}
sort(edge,edge+m);
int ans=inf;
bool flag=true;
for(int l=0;l<m;l++)
{
for(int i=1;i<=n;i++)
parent[i]=i;
un(edge[l].a,edge[l].b);
int mi=edge[l].w;
int p=1;
if(p==n-1)
{
printf("0\n");
flag=false;
break;
}
for(int r=l+1;r<m;r++)
{
if(un(edge[r].a,edge[r].b))
{
p++;
if(p==n-1)
{
ans=min(ans,edge[r].w-mi);
break;
}
}
}
}
if(flag)
printf("%d\n",ans);
}
return 0;
}