8. 그림 (하): 도로 마을 통

목차

제목 설명

코드

문제 풀이 사고 와 나타 난 문제

제목 설명
기 존의 마을 간 도로 에 대한 통계 데이터 표 에는 표준 도로 로 건설 할 수 있 는 몇 개의 도로 의 원가 가 열거 되 어 있 으 며, 모든 마을 이 도로 연결 에 필요 한 최저 원 가 를 가지 도록 한다.
입력 형식: 입력 데 이 터 는 도시 수 정수 N (≤ 1000) 과 후보 도로 수 목 M (≤ 3N) 을 포함한다.그 다음 에 M 행 은 M 개의 도로 에 대응 하여 각 줄 에 3 개의 정 수 를 주 었 는데 그것 이 바로 이 도로 가 직접 연 결 된 두 도시 의 번호 와 이 도로 개축 의 예산 비용 이다.간단하게 말하자면, 도 시 는 1 부터 N 까지 번호 가 있다.
출력 형식: 마을 통 에 필요 한 최저 비용 을 출력 합 니 다.입력 데이터 가 원활 하지 못 하면 출력 - 1 은 더 많은 도 로 를 건설 해 야 한 다 는 뜻 이다.
입력 예시:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

출력 예시:

12

코드

#include
#include
#include
#define MaxVerteNum 1000
typedef int Vertex;
typedef int WeightType; 

typedef struct ENode *PtrToENode;
struct ENode{
	WeightType Weight;
	Vertex V1;
	Vertex V2;
};
typedef PtrToENode Edge;

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
	PtrToAdjVNode Next;
	Vertex AdjV;
	WeightType Weight; /*        */
};

typedef struct HNode{
	PtrToAdjVNode FirstEdge;
}AdjList[MaxVerteNum];

typedef struct LNode *LGraph;
struct LNode{
	int Nv;
	int Ne;
	AdjList G;
};

LGraph Create( int VertexNum )
{
	Vertex V;
	LGraph Graph;
	
	Graph = (LGraph)malloc(sizeof(struct LNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	for( V=0; V!=VertexNum; ++V )
		Graph->G[V].FirstEdge = NULL;
	return Graph;
}

void InsertEdge( LGraph Graph, PtrToENode E )
{
	PtrToAdjVNode NewNode;
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V2;
	NewNode->Weight = E->Weight;
	NewNode->Next = Graph->G[E->V1].FirstEdge;
	Graph->G[E->V1].FirstEdge = NewNode;
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V1;
	NewNode->Weight = E->Weight;
	NewNode->Next = Graph->G[E->V2].FirstEdge;
	Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildGraph()
{
	LGraph Graph;
	PtrToENode E;
	Vertex V;
	int Nv, i;
	
	scanf("%d",&Nv);
	Graph = Create(Nv);
	scanf("%d",&(Graph->Ne));
	if(Graph->Ne){
		E = (PtrToENode)malloc(sizeof(struct ENode));
		for(i=0;i<Graph->Ne;++i){
			scanf("
%d %d %d",&E->V1,&E->V2,&E->Weight);
			--E->V1;
			--E->V2;
			InsertEdge( Graph, E );
		}
	}
	return Graph;
}

/* -----------       ----------- */
typedef Vertex ElementType; /*      */
typedef Vertex SetName; /*             */
typedef ElementType SetType[MaxVerteNum];

void InitializeVSet( SetType S, int N )
{
	ElementType X;
	for ( X=0; X!=N; ++X )
		S[X] = -1;
}

void Union( SetType S, SetName Root1, SetName Root2 )
{
	/*          */
	if ( S[Root1] < S[Root2] ){
		S[Root2] += S[Root1]; /*   1    2 */
		S[Root1] = Root2;
	}
	else {
		S[Root1] += S[Root2];
		S[Root2] = Root1;
	}
}

SetName Find( SetType S, ElementType X )
{ /*             -1 */
	if ( S[X] < 0 ) /*        */
		return X;
	else
		return S[X] = Find( S, S[X] ); /*      */
}

bool CheckCycle( SetType VSet, Vertex V1, Vertex V2 )
{
	Vertex Root1, Root2;
	
	Root1 = Find( VSet, V1 ); /*   V1         */
	Root2 = Find( VSet, V2 ); /*   V2         */
	
	if ( Root1 == Root2 )
		return false;
	else {
		Union( VSet, Root1, Root2 );
		return true;
	}
}
/*-----------       --------------*/

/*-----------       --------------*/
void PerDown( Edge ESet, int p, int N )
{/*     N        ， ESet[p]               */
 /*  ESet[p]             */
	int Parent, Child;
	struct ENode X;
	
	X = ESet[p];
	for( Parent = p; (Parent*2+1)<N; Parent=Child ){
		Child = Parent * 2 + 1;
		if( (Child!=N-1) && (ESet[Child].Weight>ESet[Child+1].Weight) )
			++Child;
		if( X.Weight <= ESet[Child].Weight )
			break;
		else
			ESet[Parent] = ESet[Child];
	}
	ESet[Parent] = X;
}

void InitializeESet ( LGraph Graph, Edge ESet )
{ /*         ESet，          */
	Vertex V;
	PtrToAdjVNode W;
	int ECount;
	
	/*         ESet */
	ECount = 0;
	for( V=0; V<Graph->Nv; ++V )
		for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
			if( V < W->AdjV ){
				ESet[ECount].V1 = V;
				ESet[ECount].V2 = W->AdjV;
				ESet[ECount++].Weight = W->Weight;
			}
	/*         */
	for( ECount = Graph->Ne/2-1;ECount>=0;--ECount )
		PerDown(ESet, ECount, Graph->Ne);
} 

void Swap( PtrToENode E1, PtrToENode E2 )
{
	struct ENode ETemp;
	ETemp = *E2;
	*E2 = *E1;
	*E1 = ETemp;
}

int GetEdge(Edge ESet, int CurrentSize)
{ /*         CurrentSize，               */
	Swap( &ESet[0],&ESet[CurrentSize-1] );
	PerDown( ESet, 0, CurrentSize-1 );
	return CurrentSize - 1;
}
/* ------------         --------------- */

int Kruskal( LGraph Graph, LGraph MST )
{
	WeightType TotalWeight;
	int ECount, NextEdge;
	SetType VSet;
	Edge ESet;
	
	InitializeVSet( VSet, Graph->Nv ); /*         ，          ，       */
	ESet = (Edge)malloc(sizeof(struct ENode)*Graph->Ne);
	InitializeESet( Graph, ESet ); /*          */
	
	/*                  */
	MST = Create(Graph->Nv);
	TotalWeight = 0;
	ECount = 0;
	
	NextEdge = Graph->Ne; /*           ，          */
	while ( ECount < Graph->Nv-1 ){/*             Graph->Nv-1 */
		NextEdge = GetEdge(ESet, NextEdge); /*   Weight       ，                  */
		if( NextEdge == 0 ) /*         */
			break;
		/*             ，              */
		if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )){
			/*      MST */
			InsertEdge( MST, ESet+NextEdge );
			TotalWeight += ESet[NextEdge].Weight;/*      */
			++ECount;
		}
	}
	if( ECount < Graph->Nv-1 ) /*        , while      */
		TotalWeight = -1; /*       ，         */
	return TotalWeight;
}

int main()
{
	LGraph Graph = BuildGraph();
	LGraph MST;
	int TotalWeight = Kruskal( Graph, MST );
	printf("%d", TotalWeight);
	return 0;
}

문제 풀이
1. 그림 을 만 들 고 가장자리 와 정점 을 그림 에 저장한다.2. 모든 사 이 드 저장 소 는 최소 더미 에 존재 합 니 다. 이렇게 하면 매번 Weight 의 가장 작은 사 이 드 를 꺼 내 는 데 편리 합 니 다.3. Weight 의 가장 작은 가장 자 리 를 꺼 내 서 가장 작은 더 미 를 다시 정리한다.이 쪽 이 생 성 트 리 에 삽입 되면 회로 가 있 는 지 확인 하 세 요.
문제 가 발생 한 것 은 주로 최소 더미 안에 있 고 최소 더 미 는 가장자리 가 정점 이 아니 기 때문에 필터 함수 PerDown(ESet, ECount, Graph->Ne); 를 호출 하면 여기에 쓸 수 없다 Graph->Nv.이후 에 매번 함 수 를 다 쓸 때마다 변수 가 맞 는 지 확인 해 야 한다. 그렇지 않 으 면 오류 가 발생 하면 처음부터 끝까지 검사 하 는 것 이 너무 느리다.