hdu 1233 또는 원활 한 공정 최소 생 성 트 리 (prim 알고리즘 + kruskal 알고리즘)

아니면 원활 한 공사?
                                                                           Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Problem Description
모 성에 서 마을 의 교통 상황 을 조사 하여 얻 은 통계표 에는 임의의 두 마을 간 의 거리 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 마을 간 에 도 도로 교통 을 실현 할 수 있 도록 하 는 것 이다.가장 작은 도로 의 총 길 이 를 계산 해 주세요.
 
Input
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 번 째 줄 은 마을 수 N (< 100) 을 드 립 니 다.이 어 N (N - 1) / 2 줄 은 마을 간 의 거리 에 대응 하고 각 줄 은 두 마을 의 번호 와 이 두 마을 간 의 거 리 를 나타 낸다.간단하게 말하자면, 마을 은 1 부터 N 까지 번 호 를 매 긴 다.
N 이 0 일 때 입력 이 끝나 면 이 용례 는 처리 되 지 않 습 니 다.
 
Output
각 테스트 사례 에 대해 서 는 1 줄 에서 가장 작은 도로 총 길 이 를 출력 한다.
 
Sample Input

   
   
   
   

    
    
    
    3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
5


    
    
    
    
 
     
 
      Hint 
     
Hint 
    
    
    
    
     
Huge input, scanf is recommended.
   
   
   
   

 
 무방 향 대역 권 연결 그림 G 에서 연결 서브 트 리 가 모든 정점 을 포함 하고 이 정점 을 연결 하 는 변 권 의 합 이 가장 작 으 면,
그럼 이 연결 서브 맵 은 G 의 최소 생 성 트 리 입 니 다.최소 생 성 트 리 를 구 하 는 흔 한 알고리즘 은 Prim 알고리즘 입 니 다.
prim 알고리즘 (시간 복잡 도 는 O (n ^ 3)):
Prim 알고리즘 의 기본 사상 은:
1) 두 개의 집합 V 와 S 를 설정 하고, 한 개의 정점 을 시작 점 으로 임의로 선택 하여, 시작 점 을 집합 S 에 넣 고, 나머지 정점 은 집합 에 저장한다.
V 중;2) 그리고 욕심 전략 을 사용 하여 길이 가 가장 짧 고 단점 을 각각 S 와 V 에서 선택 하 십시오 (즉, 최소 생 성 트 리 중 하나 입 니 다.
변) 이 변 이 V 에 있 는 단점 을 집합 S 에 넣는다.3) S 에 모든 정점 이 포 함 될 때 까지 2) 단 계 를 반복 한다.

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int map[100][100],s[100],vis[100];
int n,m;
int prim()
{
    int i,j,t,p,min,minpos,cnt;
    int ans=0;
    cnt=0;  /*           */
    vis[1]=1; /*        */
    s[cnt++]=1; /*s          */
    while(cnt<n)  /*       */
    {
        t=cnt;
        min=inf;
        for(i=0;i<t;i++) 
        {
            p=s[i];
            for(j=1;j<=n;j++)
            {
                if(!vis[j]&&map[p][j]<min)  /*                      ，*/
                {
                    min=map[p][j];
                    minpos=j; /*             */
                }
            }
        }
        ans+=min;  
        s[cnt++]=minpos; /*        */
        vis[minpos]=1;  
    }
    return ans;
}
int main()
{
    int u,v,w,i;
    while(~scanf("%d",&n)&&n)
    {
        m=n*(n-1)/2;
        memset(vis,0,sizeof(vis));
        memset(map,inf,sizeof(map));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            map[u][v]=w;
            map[v][u]=w;
        }
        int sum=prim();
        printf("%d
",sum);
    }
    return 0;    
}

위의 알고리즘 은 세 가지 순환 이 있 습 니 다. 시간 복잡 도 는 O (N ^ 3) 입 니 다. 욕심 전략 을 사용 하기 때문에 집합 S 에 새로운 정점 을 추가 할 때마다 V 의 각 점 에서 S 의 점 까지 의 최소 변 의 길 이 를 바 꿀 수 있 습 니 다. 따라서 하나의 배열 nearest [N] (N 은 정점 개수) 를 사용 할 수 있 습 니 다.최소 수 를 생 성 하 는 과정 에서 V 의 각 점 에서 S 중점 까지 의 최소 변 길 이 를 기록 하고, 다른 배열 adj [N] 로 이 변 의 최소 대응 하 는 인접 점 을 기록 합 니 다. 그러면 O (N) 의 시간 은 가장 짧 은 변 을 찾 고, O (N) 의 시간 에 nearest [N] 과 adj [N] 을 업데이트 할 수 있 습 니 다. 따라서 O (N ^ 2) 의 알고리즘 을 얻 을 수 있 습 니 다.

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int map[100][100];
int n,m;
/*            S,         V*/
int vis[100]; //        S 
int adj[100]; //   S        
int nearest[100];  //  V     S       
int prim()
{
	int i,j,min;
	int ans=0;
	vis[1]=1;
	for(i=2;i<=n;i++)
	{
		nearest[i]=map[1][i]; 
		adj[i]=1;
	}
	int cnt=n-1; /*      */
	while(cnt--)
	{
		min=inf;
		j=1;
		for(i=1;i<=n;i++)
		{
			if(!vis[i]&&nearest[i]<min)
			{
				min=nearest[i];
				j=i;
			}
		}
		ans+=map[j][adj[j]];
		vis[j]=1;
		for(i=1;i<=n;i++)
		{
			if(!vis[i]&&map[i][j]<nearest[i])
			{
				nearest[i]=map[i][j]; /*     */
				adj[i]=j; /*      */
			}
		}
	}
	return ans;
}
int main()
{
	int i,sum,u,v,w;
	while(~scanf("%d",&n)&&n)
	{
		memset(vis,0,sizeof(vis));
		memset(map,0,sizeof(map));
		m=n*(n-1)/2;
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			map[u][v]=map[v][u]=w;
		}
		sum=prim();
		printf("%d
",sum);
	}
	return 0 ;
}

Kruskal 알고리즘 (시간 복잡 도 O (ElogE), E 는 변수):
연결 되 지 않 은 그림 G = (V, E), V = {1, 2,..., n} 을 지정 합 니 다. Kruskal 알고리즘 구조 G 의 최소 생 성 트 리 의 기본 사상 은 다음 과 같 습 니 다.
(1) 우선 G 의 n 개 정점 을 n 개의 고립 된 연결 지점 으로 본다.
(2) 첫 번 째 변 부터 변 권 이 증가 하 는 순서에 따라 각 변 을 검사 합 니 다. 그리고 다음 방법 에 따라 두 개의 서로 다른 연결 지점 을 연결 합 니 다. k 조 변 (v, w) 을 볼 때 점 v 와 w 가 각각 현재 두 개의 서로 다른 연결 지점 T1 과 T2 의 점 이 라면 변 (v, w) 을 사용 합 니 다.T1 과 T2 를 하나의 연결 지점 으로 연결 한 다음 k + 1 개의 변 을 계속 봅 니 다. 점 v 와 w 가 현재 같은 연결 지점 에 있 으 면 k + 1 개의 변 을 직접 봅 니 다. 이 과정 은 하나의 연결 지점 만 남 았 을 때 까지 진 행 됩 니 다.
이때 G 를 구성 하 는 최소 생 성 트 리 입 니 다.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int father[100];
int n,m;
struct point
{
    int u;
    int v;
    int w;
}a[5000];
bool comp(point a1,point a2) /*         */
{
    return a1.w<a2.w;
}
void initial() /*      */
{
    for(int i=0;i<=100;i++)
        father[i]=i;
}
int find(int x)  /*     */
{
    if(father[x]==x)
        return x;
    return find(father[x]);
}
void merge(int p,int q)  /*      */
{
    int pp=find(p);
    int qq=find(q);
    if(pp!=qq)
    {
        if(pp<qq)
            father[qq]=pp;
        else
            father[pp]=qq;
    }
}
int kruskal()
{
    initial();  /*   */
    int ans=0;
    sort(a+1,a+m+1,comp); /*  */
    for(int i=1;i<=m;i++)
    {
        int x=find(a[i].u);
        int y=find(a[i].v);
        if(x!=y)  /*          */
        {
            ans+=a[i].w;
            merge(x,y); /*  */
        }
    }
    return ans;
}
int main()
{
    int i,sum;
    while(~scanf("%d",&n)&&n!=0)
    {
        m=n*(n-1)/2;
        for(i=1;i<=m;i++)
            scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
        sum=kruskal();
        printf("%d
",sum);
    }
    return 0;
}