題意
給定一張圖吗讶，求其最小生成樹中權值最大的邊
要是學習過最小生成樹的相關概念榆纽，就會發(fā)現(xiàn)這道題就是直接考察的最小生成樹动知，只不過題目沒有問你最小生成樹的邊權和晌涕，而是讓你輸出最小生成樹有幾條邊（點數(shù)-1）和權值最大的那條邊的權值。
那么什么是生成樹呢撞鹉？
In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (but see Spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself).
如上圖所示疟丙，生成樹就是在給定的圖中選取最少的邊使所有頂點連通，那么最小生成樹就是選取的邊的權值和最小鸟雏。
了解了生成樹的概念享郊，就很容易能明白生成樹只有n-1條邊，其中n表示頂點數(shù)孝鹊。
那么怎么求最小生成樹呢炊琉？
這里我介紹kruscal算法。
克魯斯卡爾算法
該算法用到的是貪心思想又活，將所有的邊按權值排序苔咪，每次都選權值最小的邊锰悼，然后判斷這條邊的兩個頂點是否屬于同一個連通塊，如果不屬于同一個連通塊悼泌，那么這條邊就應屬于最小生成樹松捉，逐漸進行下去，直到連通塊只剩下一個馆里。
kruscal算法的模板代碼如下：
const int maxn=400;//最大點數(shù)
const int maxm=10000;//最大邊數(shù)
int n,m;//n表示點數(shù)隘世，m表示邊數(shù)
struct edge{int u,v,w;} e[maxm];//u,v,w分別表示該邊的兩個頂點和權值
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int fa[maxn];//因為需要用到并查集來判斷兩個頂點是否屬于同一個連通塊
int find(int x)
{
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
int kruscal()
{
int ans=-1;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;++i) fa[i]=i;//初始化并查集
int cnt=n;
for(int i=1;i<=m;++i)
{
int t1=find(e[i].u);
int t2=find(e[i].v);
if(t1!=t2)
{
if(cnt==1) break;
fa[t1]=t2;
ans=max(ans,e[i].w);
cnt--;
}
}
return ans;
}
針對這道題，我們只需要把ans+=e[i].w改為ans=max(ans,e[i].w)就好了鸠踪，至此問題得到了解決丙者。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400;
const int maxm=10000;
int n,m;
struct edge{int u,v,w;} e[maxm];
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int fa[maxn];
int find(int x)
{
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
int kruscal()
{
int ans=-1;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;++i) fa[i]=i;
int cnt=n;
for(int i=1;i<=m;++i)
{
int t1=find(e[i].u);
int t2=find(e[i].v);
if(t1!=t2)
{
if(cnt==1) break;
fa[t1]=t2;
ans=max(ans,e[i].w);
cnt--;
}
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;++i) cin>>e[i].u>>e[i].v>>e[i].w;
cout<<n-1<<" ";//生成樹有n-1條邊
cout<<kruscal();
return 0;
}
