Hihocoder \ # 1098: 최소 생 성 트 리 2 · Kruskal 알고리즘 (* 【 템 플 릿 】)
2940 단어 최소 생 성 트 리
시간 제한:
10000ms
단일 시간:
1000ms
메모리 제한:
256MB
묘사 하 다.
작은 하 이 가 도시 의 수량 이 증가 함 에 따라 그 사이 에 사용 되 는 Prim 알고리즘 은 더 이상 사용 할 수 없 게 되 었 습 니 다. 그러나 다행히도 컴퓨터 의 분석 을 통 해 작은 하 이 는 도 로 를 건설 하기에 비교적 적합 한 노선 을 선 택 했 습 니 다. 이 수량 은 특별히 크 지 않 습 니 다.
그래서 문 제 는 '샤 오 하 이' 가 현재 N 개의 도 시 를 가지 고 있 고 그 중의 일부 도시 간 에 도 로 를 건설 하 는 비용 을 알 고 있다. 샤 오 하 이 는 최소 비용 을 들 이면 두 도시 가 모두 건설 한 도 로 를 통 해 서로 도착 할 수 있다 는 것 을 알 고 싶 어 한다.(A, B, C 세 도시 가 있다 고 가정 하면 AB 사이 와 BC 사이 에 도 로 를 건설 하면 AC 사이 도 이 두 도 로 를 통 해 연 결 될 수 있다.)
알림: 쌓 인 장점 은 언제든지 자신의 지식 창고 에서 원 하 는 것 을 추출 할 수 있다 는 것 이다!
입력
모든 테스트 포인트 (파일 입력) 가 있 고 테스트 데이터 만 있 습 니 다.
테스트 데이터 그룹 에서:
제1 행위 2 개 정수 N, M 은 소 하 이 가 가 진 도시 수 와 소 하 이 가 노선 을 선별 한 조 수 를 나타 낸다.
다음 M 줄 은 각 줄 마다 하나의 노선 을 묘사 하 는데 그 중에서 i 행 위 는 3 개의 정수 N1 i, N2 i, V i 로 이 노선 의 두 점 과 이 노선 에서 도 로 를 건설 하 는 비용 을 나타 낸다.
100% 의 데이터 에 대해 N < = 10 ^ 5, M < = 10 ^ 6 을 만족 시 키 고 임의의 i 만족 1 < = N1 i, N2 i < = N, N1 i ≠ N2 i, 1 < = V i < = 10 ^ 3.
100% 의 데 이 터 를 만족 시 키 려 면 반드시 하나의 방안 이 존재 하여 임의의 두 도시 가 서로 도착 할 수 있 도록 해 야 한다.
출력
각 조 의 테스트 데이터 에 대해 1 개의 정수 Ans 를 출력 하 는 것 은 임의의 두 도시 가 건 설 된 도 로 를 통 해 서로 최소한 필요 한 건설 비용 에 도달 할 수 있 도록 하 는 것 을 의미한다.
샘플 입력
5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185샘플 출력
92
： 10 ， 100
。
：
#include <stdio.h>
#include <string>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct node
{
int u;
int v;
int w;
bool operator <(const node &x)const
{
return w<x.w;
}
}q[1000002];
int e=0;
int fa[100002];
int findset(int x)
{
return fa[x]!=x?fa[x]=findset(fa[x]):x;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
int i, j;
for(i=0; i<m; i++ )
{
scanf("%d %d %d", &q[i].u, &q[i].v, &q[i].w );
}
sort(q, q+m);
for(i=0; i<=n; i++ )
{
fa[i]=i; //
}
int ans=0;
int cnt=0;
for(int k=0; k<m; k++)
{
if( findset(q[k].u)!=findset(q[k].v) )
{
fa[fa[q[k].u]] = fa[ q[k].v];
ans+=q[k].w;
cnt++;
if(cnt==n-1)
{
break;
}
}
}
printf("%d
", ans );
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1875 는 최소 생 성 트 리 입 니 다.그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
