POJ 1861 Network （最小生成树，kruskal， 裸题）

最小生成树，kruskal， 裸题
题目意思:
给你n个点和m条边及其权值,求一个能使图联通且单条边权最大值最小的边的集合。
输出边权的最大值，边的个数，边的起始点。

本题要点：
1、用 kruskal 来模拟，每次选择当前最小的边，如果这边的两点不在同一个集合里面，则选择这条边，
用 vis来记录这条边被选择了。用 ans 来记录所有选择的边的最大值。
2、问题输出的是这个最大值，还有选择的边是哪些。裸题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 1010;
const int MaxM = 15010;
int n, m;
int fa[MaxN];
bool vis[MaxM];struct rec
{
    int x, y, z;bool operator<(const rec& rhs) const{
    return z < rhs.z;}
}edge[MaxM];int get(int x)
{
    if(x == fa[x]){
    return x;}return fa[x] = get(fa[x]);
}int main()
{
    scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i){
    scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);}sort(edge + 1, edge + m + 1);for(int i = 1; i <= n; ++i){
    fa[i] = i;}memset(vis, false, sizeof vis);int ans = -1;int x, y, cnt = 0;for(int i = 1; i <= m; ++i){
    x = get(edge[i].x), y = get(edge[i].y);if(x == y){
    continue;}fa[x] = y;vis[i] = true;++cnt;ans = max(ans, edge[i].z);}printf("%d\n%d\n", ans, cnt);for(int i = 1; i <= m; ++i){
    if(vis[i]){
    printf("%d %d\n", edge[i].x, edge[i].y);}}return 0;
}/* 4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1 *//* 1 4 1 2 1 3 2 3 3 4 */