hdoj 1233 또는 원활 한 공정 - 최소 생 성 트 리

제목: http://acm.hdu.edu.cn/showproblem.php?pid=1233
Kruskal 로 만 들 수 있 지만 그림 의 가장자리 가 조밀 할 때 prime 를 사용 하 는 것 이 더 빠 릅 니 다.
AC 코드: 296 MS

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int inf=0xffffff;

int dis[105],sum,n;

int weight[105][105];

void prime()

{

	bool visit[105];

	int pre[105];

	memset(visit,0,sizeof(visit));

	for(int i=1;i<=n;i++)

		{dis[i]=weight[1][i];pre[i]=1;}

	visit[1]=1;

	int index,mmin;

	for(int i=1;i<=n-1;i++)

	{

		mmin=inf;

		for(int j=1;j<=n;j++)

		{

			if(!visit[j] && dis[j]<mmin)

			{

				mmin=dis[j];

				index=j;

			}

		}

		visit[index]=1;

		sum+=weight[pre[index]][index];

		for(int i=1;i<=n;i++)

		{

			if(!visit[i] && weight[index][i]<dis[i])

			{

				dis[i]=weight[index][i];

				pre[i]=index;

			}

		}

	}	

}

int main()

{



	while(scanf("%d",&n))

	{

		if(n==0)break; 

		int m=n*(n-1)/2;

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				weight[i][j]=inf;

		for(int i=0;i<m;i++)

		{

			int x,y,z;

			scanf("%d %d %d",&x,&y,&z);

			weight[x][y]=z;

			weight[y][x]=z;

		}

		sum=0;

		prime();

		cout<<sum<<endl;

	}

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 1875 는 최소 생 성 트 리 입 니 다.

그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdoj 1233 또는 원활 한 공정 - 최소 생 성 트 리 - prime 알고리즘

좋은 웹페이지 즐겨찾기