NYOJ --- 38 문제 배선 문제

이 문 제 는 최소 생 성 트 리 문제 로 prim 알고리즘 을 사용 하기 시 작 했 고 나중에 Kruskal 로 문 제 를 해결 했다.요즘 이 걸 접 하면 서 천천히 배우 지만 자신의 진 보 를 느 낄 수 있 습 니 다.이 문 제 는 사실 두 가지 방법 으로 해결 할 수 있 는데, 지금 나 는 이 두 가지 방법 을 붙 일 것 이다.공유 해 드릴 게 요.구체 적 인 문제 풀이 방향 은 쓰 지 않 겠 다.데이터 구 조 를 마음대로 뒤 집어 도 찾 을 수 있다.첫 번 째 prim 알고리즘 은 비교적 간단 하고 이해 하기 쉬 우 며 두 번 째 kruskal 알고리즘 중의 정렬 이 좀 어 려 울 수 있 습 니 다.이 따 내 가 쓸 간접 정렬 따로 정리 할 게.
원제 주소:
클릭 하여 링크 를 엽 니 다.
첫 번 째: prim 알고리즘

#include
#include
#include
#include
using namespace std;
int a[501][501],b[501];
int main()
{  
	int i,j,k,l,v,e,n,m;
	scanf("%d",&k);
	while(k--)
	{   memset(a,0,sizeof(a));
	    memset(b,0,sizeof(b));
		scanf("%d%d",&v,&e);
		while(e--)
		{
			scanf("%d%d%d",&n,&m,&l);
			a[n][m]=l;a[m][n]=l;
		}
		for(i=1;i<=v;i++)
		 scanf("%d",&b[i]);
		sort(b,b+v);
		int flat[501]={0},sum=0;
		flat[1]=1;
		for(l=1;la[n][i])
					a[1][i]=a[n][i];
			}
			sum+=a[1][n];
		}printf("%d
",sum+b[1]);
	}return 0;
}       

두 번 째: kruskal 알고리즘

#include
#include
#include
#include
using namespace std;

int n,m,v[125005],w[125005],r[125000],p[510],u[125005];
int father(int x)
{ return p[x]==x?x:p[x]=father(p[x]);}
int  comp(const int i,const int j)
{
	return w[i]

2, 3 일 을 바쁘게 보 냈 는데 이 정도 진전 은 나 는 정말 실패했다.다른 사람 이 어떻게 하 든 나 는 내 리듬 대로 할 게.
최근 에 무 라카 미 하루 키 라 는 말 을 보 니 기분 이 좋 습 니 다. 여러분 과 공유 하 겠 습 니 다.
전 세계 모든 사람들 이 어떻게 말 하든지 간 에 나 는 나의 느낌 이 옳다 고 생각한다.다른 사람 이 어떻게 보 든 지 간 에 나 는 결코 나의 리듬 을 흐 트 러 뜨리 지 않 을 것 이다.좋아 하 는 일 은 당연히 견 딜 수 있 지만, 싫어 하 는 것 은 아무리 해도 오래 가지 못 한다.