그림 이론 - 최소 생 성 트 리 문제 해결 (Kruskal 알고리즘 & Prim 알고리즘)
1. Kruskal 알고리즘
Kruskal 알고리즘 은 작성 하기 쉽 고 효율 이 높 습 니 다. 자서 p356 설명 은 다음 과 같 습 니 다.
Kruskal 알고리즘 의 첫 번 째 단 계 는 모든 변 을 작은 것 부터 큰 것 까지 순서대로 배열 하 는 것 입 니 다. 이 단 계 는 라 이브 러 리 함수 qsort 또는 sort 를 직접 사용 할 수 있 습 니 다.다음은 어 릴 때 부터 차례대로 각 변 (u, v) 을 고찰 한다.
4. 567917. 상황 1: u 와 v 가 같은 연결 분량 에 있 으 면 (u, v) 를 넣 으 면 링 이 형성 되 기 때문에 선택 할 수 없습니다
4. 567917 상황 2: u 와 v 가 서로 다른 연결 분량 에 있다 면 가입 (u, v) 이 가장 좋 을 것 이다.왜 일 까요?다음은 반증 법 을 사용 합 니 다. 이 변 을 추가 하지 않 으 면 가장 좋 은 해 를 얻 을 수 있 습 니 다. T + (u, v) 는 반드시 있 고 하나의 고리 만 있 습 니 다. 그리고 링 에 적어도 한 개의 변 (u, v) 의 가중치 가 (u, v) 의 가중치 보다 크 거나 같 습 니 다.이 쪽 을 삭제 하면 받 은 새 트 리 T = T + (u, v) - (u, v) 는 T 보다 나 쁘 지 않 습 니 다.따라서 가입 (u, v) 은 가입 하지 않 는 것 보다 나 쁘 지 않 을 것 이다
다음은 위조 코드 입 니 다.
( ) ， i e[i](1 <= i < m)
MST
，
for(int i = 0; i < m; i++) {
if(e[i].u e[i].v ) {
e[i] MST
e[i].u e[i].v
}
}
위의 위조 코드 에서 가장 관건 적 인 부분 은 '연결 분량 의 조회 와 합병' 이다. 임의의 두 점 이 같은 연결 분량 에 있 는 지, 그리고 이 두 연결 분량 을 합병 해 야 하 는 지 알 아야 한다.간단 하고 효율 적 인 알고리즘 은 이 문 제 를 처리 하 는 데 사용 할 수 있 습 니 다. 그리고 여기 서 길 을 가리 키 는 큰 사람 을 찾 아 설명 할 수 있 습 니 다. 매우 사랑 하고 집 을 찾 습 니 다. 모든 연결 분량 을 하나의 집합 으로 볼 수 있 습 니 다. 이 집합 은 연결 분량 중의 모든 점 을 포함 합 니 다.이 점 들 은 서로 통 하지만 구체 적 인 연결 방식 은 중요 하지 않다.그림 에서 모든 점 은 하나의 연결 분량 에 속 하고 집합 표시 에 대응 하 며 모든 요소 가 마침 하나의 집합 에 속한다.그림 의 모든 연결 분량 은 교차 하지 않 는 집합 으로 표시 할 수 있다 는 얘 기다.자기 의 것 을 바 치고 집 판 을 조사 하 다
#include 집합 을 찾 은 후에 Kruskal 알고리즘 의 전체 코드 는 어렵 지 않 게 제시 되 었 다.i 조 변 의 두 점 번호 와 가중치 가 각각 u [i], v [i] 와 w [i] 에 저장 되 고 정렬 후 i 작은 변 의 번 호 는 r [i] 에 저장 된다 고 가정 합 니 다.
전체 코드:
int cmp(const int i, const int j) { return w[i] < w[j]; } //
int find(int x) { return p[x] == x ? x : p[x] = find(p[x])} // find
int Kruskal() {
int ans = 0;
for(int i = 0; i < n; i++) p[i] = i; //
for(int i = 0; i < m; i++) r[i] = i;
sort(r,r+m,cmp);
for(int i = 0; i < m; i++) {
int e = r[i];
int x = find(u[e]);//
int y = find(v[e]);//
if(x != y) { // ，
ans += w[e];
p[x] = y;
}
}
return ans;
}
연습 문제:
번호
제목 이름 (영어)
비고
hdu1863
원활 한 공사
나무판 자 문제 최소 생 성
hdu1879
계속 원활 한 공사
나무판 자 문제 최소 생 성
hdu1875
원활 한 공사 재 개
나무판 자 문제 최소 생 성
낙 곡 P3366
【 템 플 릿 】 최소 생 성 트 리
나무판 자 문제 최소 생 성
1. hdu 1863 원활 한 공사
Problem Description 성 정부의 '원활 한 공사' 목 표 는 성 전체 두 마을 간 에 도로 교통 을 실현 할 수 있 도록 하 는 것 이다.조사 평 가 를 통 해 얻 은 통계 표 에는 도 로 를 건설 할 수 있 는 몇 개의 도로 비용 이 열거 되 어 있다.지금 당신 이 프로그램 을 작성 하여 성 전체 가 원활 하 게 통 하 는 데 필요 한 최저 원 가 를 계산 해 주 십시오.Input 테스트 입력 에는 몇 가지 테스트 용례 가 포함 되 어 있 습 니 다.각 테스트 용례 의 첫 줄 에 평 가 된 도로 개수 N, 마을 수 M (< 100) 을 제시 합 니 다.그 다음 에 N 행 은 마을 간 도로 의 원가 에 대응 하여 각 줄 에 한 쌍 의 정 수 를 제시 했다. 각각 두 마을 의 번호 와 이 두 마을 간 도로 의 원가 (정수) 이다.간단하게 말하자면, 마을 은 1 부터 M 까지 번호 가 있다.N 이 0 일 때 모든 입력 이 끝나 고 해당 결 과 는 출력 하지 마 십시오.Output 은 모든 테스트 사례 에 대해 1 줄 에서 성 전체 가 원활 하 게 통 하 는 데 필요 한 최소 비용 을 출력 합 니 다.통계 데이터 가 원활 함 을 보장 하지 못 하면 출력 "?"
#include 2. hdu 1879 계속 원활 한 공사
이 문 제 는 위의 문제 에 비해 이미 만들어 진 도 로 를 0 으로 설정 하면 되 며, 동시에 본 문제 의 입 출력 은 cincout 를 사용 할 수 없 을 것 같 아서 시간 을 초과 할 수 있 습 니 다.
Problem Description 성 정부의 '원활 한 공사' 목 표 는 성 전체 두 마을 간 에 도로 교통 을 실현 할 수 있 도록 하 는 것 이다.현재 도시 도로 통계 표를 얻 었 는데 표 에는 임의의 두 도시 간 에 도 로 를 건설 하 는 비용 과 이 도로 가 이미 뚫 렸 는 지 의 상태 가 열거 되 어 있다.지금 당신 이 프로그램 을 작성 하여 성 전체 가 원활 하 게 통 하 는 데 필요 한 최저 원 가 를 계산 해 주 십시오.Input 테스트 입력 에는 몇 가지 테스트 용례 가 포함 되 어 있 습 니 다.각 테스트 용례 의 첫 번 째 줄 은 마을 수 N (1 < N < 100) 을 드 립 니 다.그 다음 에 N (N - 1) / 2 줄 은 마을 간 도로 의 원가 와 건설 상태 에 대응 하여 각 줄 에 4 개의 정 수 를 주 었 는데 각각 두 마을 의 번호 (1 번호 에서 N 까지) 이다. 이 두 마을 간 도로 의 원가 와 건설 상 태 는 1 은 이미 건설 되 었 고 0 은 건설 되 지 않 았 음 을 나타 낸다.N 이 0 일 때 입력 이 끝 납 니 다.Output 의 모든 테스트 용례 의 출력 은 한 줄 을 차지 하고 전 성의 원활 한 출력 에 필요 한 최저 원 가 를 차지한다.
#include
",ans);
}
return 0;
}
3. hdu 1875 원활 한 공사 재 개
먼저 모든 정점 을 입력 한 다음 에 두 개의 정점 이 적당 한 변 을 구성 할 수 있 는 지 판단 한다.
Problem Description '백도 호' 라 는 곳 에 대해 들 어 보 셨 을 거 라 고 믿 습 니 다. 백도 호 주민 들 은 서로 다른 섬 에 살 고 있 습 니 다. 다른 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 집 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 발전 에 있어 서 먼저 해결 해 야 할 문 제 는 당연히 교통 문제 이다. 정 부 는 백도 호의 원활 한 소통 을 실현 하기 로 결정 했다!탐사 팀 RPRush 를 통 해 백도 호의 상황 을 충분히 파악 한 뒤 조건 에 맞 는 작은 섬 사이 에 다 리 를 놓 기로 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 거리 가 10m 보다 작 으 면 안 되 고 1000 m 이상 이면 안 된다 는 것 이다.물론 돈 을 아 끼 기 위해 서 는 임 의 2 개 작은 섬 사이 에 길이 있 으 면 된다.그 중 다리 의 가격 은 미터 당 100 위안 이다.Input 입력 은 여러 그룹의 데 이 터 를 포함한다.입력 은 먼저 정수 T (T < = 200) 를 포함 하고 T 조 데이터 가 있 음 을 의미 합 니 다.각 조 의 데 이 터 는 먼저 하나의 정수 C (C < = 100) 로 작은 섬의 개 수 를 대표 하고 그 다음은 C 조 좌표 로 모든 작은 섬의 좌 표를 대표 한다. 이런 좌 표 는 모두 0 < = x, y < = 1000 의 정수 이다.Output 각 조 의 입력 데이터 출력 줄 은 다 리 를 건설 하 는 최소 비용 을 대표 하고 결 과 는 작은 숫자 를 유지 합 니 다.모든 원활 한 공 사 를 이 루 지 못 하면 수출 "oh!".
#include
",ans);
else printf("oh!
");
}
return 0;
}
4. 낙 곡 P3366 【 템 플 릿 】 최소 생 성 트 리
판자 문제
#include
");
else printf("%d
",ans);
return 0;
}
2. Prim 알고리즘
진 월 할머니 의 데이터 구조 인 Prim 알고리즘 의 기본 적 인 사고방식 은 하나의 노드 에서 시작 하여 작은 나 무 를 자라 게 하 는 것 이다.Dijkstra 알고리즘 과 비슷 합 니 다.Dijkstra 알고리즘 위조 코드:
void Dijkstra(Vertex s) {
while(1) {
V = dist
if ( V )
break;
collected[V] = true;// V
for(V W) {
if(collected[W] == false && dist[V] + E(V,W) < dist[W]) {
dist[W] = dist[V]+E<V,W>;
path[W] = V;
}
}
}
Prim 알고리즘 위조 코드:
void Prim(Vertex s) {
while(1) {
V = dist
if ( V )
break;
V MST
for(V W) {
if(W && E(V,W) < dist[W]) {
dist[W] = E<V,W>;
parent[W] = V;
}
}
}
전체 코드
double edge[maxn][maxn];// ~
int vis[maxn];//
double dist[maxn];
double ans;
double Prim() {
for(int i = 2; i <= n; i++) {
dist[i] = edge[1][i];// dist 1
}
vis[1] = 1;//// 1 vis[i] == 0
for(int i = 2; i <= n; i++) {
int min = INF;
int v = -1;
for(int j = 2; j <= n; j++) {// v———— dist
if(!vis[j] && dist[j] < min) {
min = dist[j];
v = j;
}
}
if(v != -1) {// v~ MST
vis[v] = 1;
ans += dist[v];
for(int j = 2;j <= n; j++) {// dist
if(!vis[j] && edge[v][j] < dist[j]) {//
dist[j] = edge[v][j];
}
}
}
}
return ans;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
