HDU 1233 또는 원활 한 프로젝트 (최소 생 성 트 리 Prime & Kruskal)
3060 단어 알고리즘데이터 구조최소 생 성 트 리문제 해결 의 길
prime 알고리즘
#include
#include
#include
using namespace std;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
int dis[maxn], n, mp[maxn][maxn];
bool vis[maxn];
void prim() {
for(int i = 1; i <= n; i++) {
dis[i] = mp[1][i];
}
int ans = 0;
dis[1] = 0;
vis[1] = true;
for(int i = 2; i <= n; i++) {
int u = INF;
int pos;
for(int j = 1; j <= n; j++) {
if(!vis[j] && u > dis[j]) {
u = dis[j];
pos=j;
}
}
if(u == INF) break;
vis[pos] = true;
ans += u;
for(int j = 1; j <= n; j++) {
if(!vis[j] && dis[j]>mp[pos][j]) {
dis[j] = mp[pos][j];
}
}
}
printf("%d
", ans);
}
int main() {
while(scanf("%d", &n) && n) {
memset(vis, false, sizeof(vis));
int m = (n-1)*n/2;
while(m--) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
mp[u][v] = mp[v][u] = w;
}
prim();
}
return 0;
}
Kruskal 알고리즘
#include
#include
#include
#include
using namespace std;
const int MAXN = 10005;
int father[MAXN];
struct node {
int u, v, value;
}mp[MAXN];
bool cmp(node a, node b) {
return a.value < b.value;
}
int Find(int x) {
if(father[x] == x)
return father[x];
return father[x] = Find(father[x]);
}
void Union(int a, int b) {
int fa = Find(a);
int fb = Find(b);
if(fa != fb) {
father[fb] =fa;
}
}
int Kruskal(int n, int m) {
sort(mp, mp + m, cmp);
for(int i = 0; i <= n; i++) {
father[i] = i;
}
int ans = 0;
for(int i = 0; i < m; i++) {
int fa = Find(mp[i].u);
int fb = Find(mp[i].v);
if(fa != fb) {
Union(mp[i].u, mp[i].v);
ans += mp[i].value;
}
}
return ans;
}
int main() {
int n;
while(scanf("%d", &n) && n) {
int m = n*(n-1)/2;
for(int i = 0; i < m; i++) {
scanf("%d %d %d", &mp[i].u, &mp[i].v, &mp[i].value);
}
printf("%d
", Kruskal(n, m));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.