游客 注册 | 登录
中文 | En

1363 - 算法7-9：最小生成树

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB
最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。
可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。
而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。以下是其算法的大致结构： 

<span style="font-family:宋体;">在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。</span>


<span></span>

题目输入

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。

题目输出

只有一个整数，即最小生成树的总代价。请注意行尾输出换行。

输入/输出样例

输入格式

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

输出格式

6

C语言解答

#include<stdio.h> 
#define MAX_VERTEX_NUM 100
int parent[MAX_VERTEX_NUM];
typedef struct  
{  
    int weight;  
    int begin;  
    int end;   
}Edge;
int Find(int *parent,int f)
{
    while(parent[f]>0)
      f=parent[f];
    return f;
}
int main()
{    
     int N,num,k=0,sum=0,m,n;
     
     Edge edges[MAX_VERTEX_NUM*MAX_VERTEX_NUM],temp;
     scanf("%d",&N);
     for(int i=0;i<N;i++)
	 {
	    for(int j=0;j<N;j++)
		{ 
             scanf("%d",&num);  
             if(num!=0&&i<j)  
             {  
                 edges[k].weight=num;  
                 edges[k].begin=i;  
                 edges[k].end=j;  
                 k++;  
             }  
        }  
    }
    for(int i=0;i<k;i++)  
    {  
        for(int j=i;j<k;j++)  
        {  
            if(edges[i].weight>edges[j].weight)  
            {  
                temp.weight=edges[i].weight;  
                temp.begin=edges[i].begin;  
                temp.end=edges[i].end;  
                edges[i].weight=edges[j].weight;  
                edges[i].begin=edges[j].begin;  
                edges[i].end=edges[j].end;  
                edges[j].weight=temp.weight;  
                edges[j].begin=temp.begin;  
                edges[j].end=temp.end;  
            }  
        }  
    }
    for(int i=0;i<N;i++)
    {
        parent[i]=0;
    }
    for(int i=0;i<k;i++)
    {
        n=Find(parent,edges[i].begin);
        m=Find(parent,edges[i].end);
        if(n!=m)
        {
           parent[n]=m;
           sum+=edges[i].weight;
        }
    }
    printf("%d\n",sum);
    return 0;
}

C++解答

#include <cstdio>
#include <cstdlib>
const int MAXN = 50;		// 最大顶点数
const int INF = 1000000000;	// 作为标记的无穷大值
int mat[MAXN][MAXN];		// 无向图的邻接矩阵
int mind[MAXN]; 			// 辅助数组
int v[MAXN];				// 标记顶点是否被访问过的数组
int n;						// 顶点的个数
int prim() {
	int ret = 0, i, j, k;
	for (i = 0; i<n; i++) {
		mind[i] = INF;
		v[i] = 0;
	}
	for (mind[j = 0] = 0; j < n; j++) {
		for (k = -1, i = 0; i < n; i++) {
			if (!v[i] && (k == -1 || mind[i] < mind[k])) {
				k = i;
			}
		}
		v[k] = 1;
		ret += mind[k];
		for (i = 0; i < n; i++) {
			if (!v[i] && mat[k][i] < mind[i]) {
				mind[i] = mat[k][i];
			}
		}
	}
	return ret;
}
int main() {
	scanf("%d", &n);
	for (int i = 0;i < n;i++) {
	// 读入无向图的邻接矩阵
		for (int j = 0;j < n;j++) {
			scanf("%d", &mat[i][j]);
			if (mat[i][j] == 0)
				mat[i][j] = INF;
		}
	}
	printf("%d\n", prim());
	return 0;
}

Java解答

import java.util.Scanner;

public class Main {

	/**
	 * 4
	 * 0 2 4 0
	 * 2 0 3 5
	 * 4 3 0 1
	 * 0 5 1 0
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[][] weight = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				weight[i][j] = in.nextInt();
			}
		}
		Prim prim = new Prim(n);
		MinTree minTree = new MinTree();
		minTree.create(n, prim, weight);
		minTree.prim(prim, 0);
	}
	
	private static class MinTree{
		public int[] visited;
		public int len;
		
		public void create(int vertx, Prim prim, int[][] weight) {
			this.len = vertx;
			this.visited = new int[len];
			prim.weight = weight;
		}
		
		public void prim(Prim prim, int v) {
			this.visited = new int[len];
			visited[v] = 1;
			int min;
			int t = -1;
			int res = 0;
			for (int i = 1; i < len; i++) {
				min = Integer.MAX_VALUE;
				for (int j = 0; j < len; j++) {
					for (int k = 0; k < len; k++) {
						if (prim.weight[j][k] != 0 && visited[j] == 1 && visited[k] == 0 && prim.weight[j][k] < min) {
							t = k;
							min = prim.weight[j][k];
						}
					}
				}
				if (t != -1) {
					visited[t] = 1;
					res += min;
				}
			}
			System.out.println(res);
		}
	}
	
	private static class Prim{
		int[][] weight;
		int vertx;
		
		public Prim(int vertx) {
			this.vertx = vertx;
			this.weight = new int[vertx][vertx];
		}
	}
}
请先登陆