poj 1251

  在n个城市之间铺设光缆，铺设光缆费用很高且各个城市之间铺设光缆的费用不同。如果设计目标是使这n个城市之间的任意两个城市都可以直接或间接通信，并且要使铺设光缆的费用最低，这样的问题就是一个求最小生成树的问题。解决这个问题的方法就是在有n个城市结点、n(n-1)/2条费用不同的边构成的无向连通图中找出最小生成树。

    最小生成树的应用相当广泛，是图论中比较基础的算法。解决最小生成树有两种算法：prim和kruskal。

    prim的思想：

    设置两个集合U和V，U中存放图G中最小生成树的结点集合，V是整个结点集合。初始令U ={u0}，设u0为起始点（任意设定）。从U和V/U的带权边中找出最小权值的边<u,v>，并将结点v加入到集合U中，当U=V时，构造完毕。

    prim的设计：主要是一个lowCost数组用来存放由U到V/U的边的权值，已加入到U中的设为-1。

int prim()												//复杂度O(N^2)
{
	int result = 0;
	int minCost;
	int i,j,k;
	lowCost[0] = -1;									//从结点0开始
	for(i = 1; i< n; i++)
		lowCost[i] = graph[0][i];
	for(i = 1; i < n; i++)								//找n-1条边
	{
		minCost = MAX;
		for(j = 1; j < n; j++)							//找两个不想交集合的最小边
		{
			if(lowCost[j]>0 && lowCost[j]<minCost)
			{
				minCost = lowCost[j];
				k = j;
			}
		}
		lowCost[k] = -1;								//找到，标记
		result += minCost;
		for(j = 1; j < n; j++)							//加入这个结点后，更新两个集合的边。
		{
			if(graph[k][j] < lowCost[j])
				lowCost[j] = graph[k][j];
		}
	}
	return result;
}

 

 

自己写的prime的模板如下：

void prim()
{
    int i, j, now, min_node, min_edge;
    for(i = 1; i <= n; i ++)
        dis[i] = inf;
    now = 1;
    ans = 0;
    for(i = 1; i < n; i ++)
	{
        dis[now] = -1;
        min_edge = inf;
        for(j = 1; j <= n; j ++)
            if(now != j && dis[j] >= 0)
			{
                dis[j] = min(dis[j], map[now][j]);
                if(dis[j] < min_edge)
				{
                    min_edge = dis[j];
                    min_node = j;
                }
            }
			now = min_node;
			ans += min_edge;
    }
}

 

 

 

poj 1251题意如下：

问题描述：
Lagrishan的一个热带岛屿上的行政长官有一个问题要解决。他决定把几年前得到的外国援助资金用于修建村庄之间的道路。但是丛林比道路多太多了，使道路网络的维护太过于昂贵了。理事会必须选择停止维修一些道路。上述左侧图显示当前所有使用中的道路，以及现在每月的维护费用。当然，村庄之间必需有一些公路能够相通，即使路线并不像以前一样短。行政长官想告诉理事会怎样才使每月的花费最小，并且所维持的道路，将连接所有村庄。上面的地图标记了村庄A到I。右边的图显示了每月能够维护道路的最小费用为216aacms。你的任务是编写一个程序，将解决这些问题。
输入：
输入包含的数据集个数在100以内，以0作为最后一行。每个数据集的第一行只包含一个表示村庄个数的数n，1<n<27，并且这n个村庄是由大写字母表里的前n个字母表示。接下来的n- 1行是由字母表的前n-1个字母开头。最后一个村庄表示的字母不用输入。对于每一行，以每个村庄表示的字母开头，然后后面跟着一个数字，表示有多少条道路可以从这个村到后面字母表中的村庄。如果k是大于0，表示该行后面会表示k条道路的k个数据。每条道路的数据是由表示连接到另一端村庄的字母和每月维修该道路的花费组成。维修费用是正整数的并且小于100。该行的所有数据字段分隔单一空白。该公路网将始终连接所有的村庄。该公路网将永远不会超过75条道路。没有任何一个村庄会有超过15条的道路连接到其他村庄（之前或之后的字母）。在下面的示例输入，其中第一个数据集是与上面的地图相一致的。

 

 

一看就知道是最小生成树...

注意以下几点：1、建图（尤其是读入数据的时候，因为既有字母，又有数字，所以处理很重要，注意回车）

                 注意这是无向图

              2、 prim算法内的循环次数 ，注意只有n-1条边 

代码如下：

#include<iostream>。
using namespace std;
const int Max = 30;
const int inf = 0xfffffff;

int n, ans;
int map[Max][Max], dis[Max];

int min(int a, int b)
{
    return a < b ? a : b;
}

void prim()
{
    int i, j, now, min_node, min_edge;
    for(i = 1; i <= n; i ++)
        dis[i] = inf;
    now = 1;
    ans = 0;
    for(i = 1; i < n; i ++)
	{
        dis[now] = -1;
        min_edge = inf;
        for(j = 1; j <= n; j ++)
            if(now != j && dis[j] >= 0)
			{
                dis[j] = min(dis[j], map[now][j]);
                if(dis[j] < min_edge)
				{
                    min_edge = dis[j];
                    min_node = j;
                }
            }
			now = min_node;
			ans += min_edge;
    }
}

int main()
{
    int i, j, num, edge;
    char u, v;
    while(scanf("%d", &n) && n != 0)
	{
        for(i = 1; i <= n; i ++)
            for(j = 1; j <= n; j ++)
                map[i][j] = inf;
			for(i = 1; i < n; i ++)
			{
				scanf(" %c%d", &u, &num);   // 这里或用cin，代替scanf("%c %d", &u, &num); getchar()。
				while(num --)
				{
					scanf(" %c%d", &v, &edge);   //  同上。
					map[u-'A'+1][v-'A'+1] = edge;
					map[v-'A'+1][u-'A'+1] = edge;
				}
			}
			prim();
			printf("%d\n", ans);
    }
    return 0;
}

 

 

 未完待续，关于最小生产树问题还有很多……