poj - 1287 제목 물이 아니 라 데이터 가 약 합 니 다.
그러나 제목 에서 말 하 는 변 은 무한 할 수 있 습 니 다 (The number of possible routes is unlimited). 변 이 많 으 면 어떻게 해 야 합 니까?
물론 여 기 는 10000 개 이상 열 면 됩 니 다. 테스트 용례 가 제한 되 어 있 기 때문에 10 ^ 10 개 를 넣 을까요?
여기 서 최대 50 개의 점 을 말 하면 최대 1225 개의 변 이 고 아무리 많아 도 중복 되 는 것 이다. 실제로 우 리 는 이렇게 큰 공간 만 열 면 된다. 그리고 모든 변 을 읽 고 중복 되 는 최소 값 을 저장 하면 된다.
하지만 여 기 는 필요 없어 요. 변 수가 적어 서...
직접 코드, 이 문 제 를 알 고 싶 으 면 먼저 데이터 구 조 를 보고 집합 을 찾 아야 합 니 다. 그러나 이 문 제 는 플 렘 알고리즘 을 사용 하 는 것 이 더 빠 를 수 있 습 니 다. 점 이 적 기 때문에 o (n ^ 2).
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define nMaxEdgeNum 15000 //
#define nMaxPointNum 100 //
int father[nMaxPointNum]; //
int rank[nMaxPointNum]; //
typedef struct EDGE
{
int u, v, w;
}Edge;
Edge edge[nMaxEdgeNum];
int p, r, sum;
//
bool cmp(Edge a, Edge b)
{
return a.w < b.w;
}
//
//
void Init(int n)
{
for (int i = 1; i <= n; ++ i)
{
father[i] = i;
rank[i] = 0;
}
}
//
int Find(int x)
{
if (x != father[x])
{
father[x] = Find(father[x]);
}
return father[x];
}
//
void Union(int x, int y)
{
int xx = Find(x);
int yy = Find(y);
if (rank[xx] > rank[yy])
{
father[yy] = xx;
}
else
{
father[xx] = yy;
if (rank[xx] == rank[yy])
{
rank[yy] ++;
}
}
}
//
void Kruskal()
{
sum = 0;
Init(p);
sort(edge + 1, edge + r + 1, cmp);
for (int i = 1; i <= r; ++ i)
{
if (Find(edge[i].u) != Find(edge[i].v))
{
sum += edge[i].w;
Union(edge[i].u, edge[i].v);
}
}
printf("%d
",sum);
}
int main()
{
while (scanf("%d", &p) && p)
{
scanf("%d", &r);
for (int i = 1; i <= r; ++ i)
{
scanf("%d %d %d",&edge[i].u, &edge[i].v, &edge[i].w);
}
Kruskal();
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
