题目描写叙述：

已知一个无向带权图，求最小整数k。使仅使用权值小于等于k的边，节点1能够与节点n连通。

输入：

输入包括多组測试用例。每组測试用例的开头为一个整数n(1 <= n <= 10000)。m(1 <= m <= 100000)。代表该带权图的顶点个数，和边的个数。

接下去m行，描写叙述图上边的信息。包含三个整数,a(1 <= a <= n),b(1 <= b <= n),c(1 <= c <= 1000000),表示连接顶点a和顶点b的无向边。其权值为c。

输出：

输出为一个整数k，若找不到一个整数满足条件。则输出-1。

例子输入：

3 3
1 3 5
1 2 3
2 3 2
3 2
1 2 3
2 3 5
3 1
1 2 3

例子输出：

3
5
-1

分析：

并查集+最小生成树：运用并查集依据题目数据联立顶点，然后对边排序，贪心的从最小边開始找，再查看题目要求的1节点和n节点是否连接就可以

#include
#include
#include
#include "queue"
#include "vector"
#include "string"
#include "algorithm"
#include
#include "stack"
#include
#include

using namespace std;

class Edge
{
public:
Edge()
{
dst = 0;
}
int avex;
int bvex;
int dst;
bool operator <(const Edge &mode) const
{
return dst<mode.dst;
}
};

Edge edge[111000];

class UFSet
{
public:
UFSet(int nsize)
{
parent = new int[nsize + 1];
}
~UFSet()
{
delete[] parent;
parent = NULL;
}

// 初始化每一个顶点的祖先为自身  
void makeSet(int n);

// 找到元素x的祖先元素  
int findSet(int x);

void makeMST(int m, int n);  

private:
int *parent;//存放祖先节点，比如x=parent[i]，元素i的祖先节点为元素x

};

void UFSet::makeSet(int n) //初始化
{
for (size_t i = 1; i <= n; i++)
parent[i] = i;
}

int UFSet::findSet(int x)
{

if (parent\[x\] == x)  
    return x;

parent\[x\] = findSet(parent\[x\]);  
return parent\[x\];  

}

void UFSet::makeMST(int m, int n)
{
sort(edge + 1, edge + m + 1);//必须先对边排序（依据边的修建费用），这样才干贪心的形成最小花费

for (int i = 1; i <= m; i++)  
{  
    int baseA = findSet(edge\[i\].avex);//找到集合中的最高祖先  
    int baseB = findSet(edge\[i\].bvex);

    if (baseA != baseB)//两个顶点仅仅要不在一个集合就能够採用这条边。并合并两个集合  
        parent\[baseA\] = baseB;//合并两个最高祖先

    if (findSet(n) == findSet(1))  
    {  
        cout << edge\[i\].dst << endl;  
        return;  
    }  
}  
cout << "-1" << endl;  

}
int main()
{
int n = 0, m = 0;
while (cin >> n >> m)
{
UFSet uset(n);
uset.makeSet(n);//初始化每一个城市的祖先为自身
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &edge[i].avex, &edge[i].bvex, &edge[i].dst);
uset.makeMST(m, n);
}
return 0;
}
/**************************************************************
Problem: 1545
User: EbowTang
Language: C++
Result: Accepted
Time:650 ms
Memory:2820 kb
****************************************************************/

注：本博文为EbowTang原创，兴许可能继续更新本文。假设转载，请务必复制本条信息！

原文地址：http://blog.csdn.net/ebowtang/article/details/50536944

原作者博客：http://blog.csdn.net/ebowtang