SPOJ:368 Cobbled streets
2063 단어 최소 생 성 트 리kruskal병 찰 집욕심법
여기 서 내 가 사용 하 는 것 은 크 루스 칼 알고리즘 이다.
kruskal 알고리즘 이 사용 하 는 탐욕 준칙 은 남 은 변 에서 순환 도로 가 생기 지 않 는 최소 비용 을 가 진 변 을 선택 하여 선택 한 변 의 집합 에 가입 하 는 것 입 니 다.선택 한 변 에 순환 도로 가 생기 면 생 성 나무 가 형성 되 지 않 는 다 는 것 을 알 게 되 었 다.kruskal 알고리즘 은 e 단계 로 나 뉘 는데 그 중에서 e 는 네트워크 의 가장자리 수량 입 니 다.소모 가 점차 증가 하 는 순서에 따라 이 e 변 을 고려 하고 매번 한 변 을 고려한다.어떤 쪽 을 고려 할 때 선택 한 쪽 의 집합 에 넣 으 면 순환 도로 가 나타 나 면 버 리 고 그렇지 않 으 면 선택 합 니 다.
집합 처리 로 고리 가 생 겼 는 지 확인 합 니 다.
father [find (a)] = find (b);여 기 는 두 개의 나무 뿌리 가 합 쳐 져 서 처음에는 WA 에 주의 하지 않 았 다.
생 성 트 리 변수 가 n - 1 에 도 착 했 을 때 최소 생 성 트 리 가 되 었 음 을 설명 하고 바로 뛰 어 나 올 수 있 습 니 다.이렇게 사용 할 때 는 좀 적 을 것 이다.
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Edge
{
int u,v,cost;
};
Edge a[300005];
int father[1005]={0};
int n,m;
bool cmp(Edge a,Edge b)
{
return a.cost<b.cost;
}
void init_union_find()
{
for(int i=1;i<=n;++i)
father[i]=i;
}
int find(int p)
{
return father[p]==p?p:find(father[p]);
}
void unite(int a,int b)
{
father[find(a)]=find(b);
}
void Kruskal(int &ans)
{
sort(a,a+m,cmp);
init_union_find();
int count=0;
for(int i=0;i<m;++i)
{
Edge t=a[i];
if(find(t.u)!=find(t.v))
{
unite(t.u,t.v);
ans+=t.cost;
count++;
if(count==n-1) break;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int p,ans=0;
scanf("%d%d%d",&p,&n,&m);
for(int i=0;i<m;++i)
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].cost);
Kruskal(ans);
printf("%d
",p*ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1875 는 최소 생 성 트 리 입 니 다.그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
