poj 1861 network
사고방식: 최소 생성 트리 + 및 집합 + 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.