BZOJ1083: [SCOI2005]繁忙的都市

题意
给定一张图，求其最小生成树中权值最大的边

---

要是学习过最小生成树的相关概念，就会发现这道题就是直接考察的最小生成树，只不过题目没有问你最小生成树的边权和，而是让你输出最小生成树有几条边（点数-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).

Paste_Image.png

如上图所示，生成树就是在给定的图中选取最少的边使所有顶点连通，那么最小生成树就是选取的边的权值和最小。

---

了解了生成树的概念，就很容易能明白生成树只有n-1条边，其中n表示顶点数。
那么怎么求最小生成树呢？
这里我介绍kruscal算法。

---

克鲁斯卡尔算法
该算法用到的是贪心思想，将所有的边按权值排序，每次都选权值最小的边，然后判断这条边的两个顶点是否属于同一个连通块，如果不属于同一个连通块，那么这条边就应属于最小生成树，逐渐进行下去，直到连通块只剩下一个。

---

kruscal算法的模板代码如下：

const int maxn=400;//最大点数
const int maxm=10000;//最大边数
int n,m;//n表示点数，m表示边数
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;
}