poj 1861 network

1642 단어
클릭하여 링크 열기poj1861
사고방식: 최소 생성 트리 + 및 집합 + 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
%d
" , e[num[cnt-1]].value , cnt); for(int i = 0 ; i < cnt ; i++) printf("%d %d
" , 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; }

좋은 웹페이지 즐겨찾기