poj 1861 network

点击打开链接poj 1861

思路：最小生成树+并查集+kruskal

分析：

1 模板题，只要按照kruskal的思路即可。

2 题目要求输出的是最小生成树中最大边的最小值，以及多少条边和边的点

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 15010

int n , m;
int num[MAXN];
int father[MAXN];
int rank[MAXN];
struct Edge{
   int x;
   int y;
   int value;
}e[MAXN];

bool cmp(Edge e1 , Edge e2){
    return e1.value < e2.value;
}

void init_Set(){
    for(int i = 0 ; i <= n ; i++){
       father[i] = i;
       rank[i] = 0;
    }
}

int find_Set(int x){
    if(father[x] != x)
       father[x] = find_Set(father[x]);
    return father[x];
}

void union_Set(int x, int y){
     if(rank[x] > rank[y])
         father[y] = x;
     else{
         if(rank[x] == rank[y])
             rank[y]++;
         father[x] = y;
     }
}

void kruskal(){
     init_Set();
     sort(e , e+m , cmp);
     int cnt = 0;
     for(int i = 0 ; i < m ;i++){
         int root_x = find_Set(e[i].x);
         int root_y = find_Set(e[i].y);
         if(root_x != root_y){
            union_Set(root_x , root_y);
            num[cnt++] = i;
         } 
     }
     printf("%d\n%d\n" , e[num[cnt-1]].value , cnt);
     for(int i = 0 ; i < cnt ; i++)
         printf("%d %d\n" , e[num[i]].x , e[num[i]].y);
}

int main(){
    while(scanf("%d%d" , &n , &m) != EOF){
        for(int i = 0 ; i < m ; i++)
          scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value);
        kruskal();
    }
    return 0;
}