[usaco]Agri-Net(使用最小生成树算法)

Agri-Net
Russ Cox
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.

Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.

Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.

The distance between any two farms will not exceed 100,000.

PROGRAM NAME: agrinet
INPUT FORMAT
Line 1:  The number of farms, N (3 <= N <= 100). 
Line 2..end:  The subsequent lines contain the N x N connectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some
lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem. 

SAMPLE INPUT (file agrinet.in)
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

OUTPUT FORMAT
The single output contains the integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

SAMPLE OUTPUT (file agrinet.out)
28

------------------
这个问题就是让求最小生成树。
利用prim 算法,或者kruskal算法即可。
鉴于节点的总个数小于等于100,可以使用一个常量数组
我的解法
----------------

/*
ID:yunleis2
PROG:agrinet
LANG:C++
*/
#include<iostream>
#include<fstream>

using namespace std;
/************************************************************************/
/* minimal spinning tree                                                                     */
/************************************************************************/
int metri[101][101];
int destance[101];
bool intree[101];
int main()
{
	fstream fin("agrinet.in",ios::in);
	int N;
	fin>>N;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			fin>>metri[i][j];
		}
		destance[i]=0;
		intree[i]=false;
	}
	int sum=0;
	for(int i=0;i<N;i++)
	{
		if(!intree[i])
		{
			intree[i]=true;
			for(int j=0;j<N;j++)
			{
				destance[j]=metri[i][j];
			}
			while(true)
			{
				int ptr=-1;
				for(int j=0;j<N;j++)
				{
					if(ptr==-1||destance[ptr]==0||(intree[ptr]))
						ptr=j;
					else if((!intree[j])&&destance[j]<destance[ptr])
						ptr=j;
				}
				if(intree[ptr])
					break;
				intree[ptr]=true;
				sum+=destance[ptr];
				for(int j=0;j<N;j++)
				{
					if((!intree[j])&&(destance[j]>metri[ptr][j]))
					{
						destance[j]=metri[ptr][j];
					}
				}
			}
		}
	}
	fstream fout("agrinet.out",ios::out);
	fout<<sum<<endl;
	//system("pause");

}

测试:

USER: Ma yunlei [yunleis2]
TASK: agrinet
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3064 KB]
   Test 2: TEST OK [0.000 secs, 3064 KB]
   Test 3: TEST OK [0.000 secs, 3064 KB]
   Test 4: TEST OK [0.000 secs, 3064 KB]
   Test 5: TEST OK [0.000 secs, 3064 KB]
   Test 6: TEST OK [0.000 secs, 3064 KB]
   Test 7: TEST OK [0.000 secs, 3064 KB]
   Test 8: TEST OK [0.000 secs, 3064 KB]
   Test 9: TEST OK [0.000 secs, 3064 KB]
   Test 10: TEST OK [0.000 secs, 3064 KB]

All tests OK.
YOUR PROGRAM ('agrinet') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.

 

时间: 2011-08-14

[usaco]Agri-Net(使用最小生成树算法)的相关文章

[算法系列之二十七]Kruskal最小生成树算法

简介 求最小生成树一共有两种算法,一个是就是本文所说的Kruskal算法,另一个就是Prime算法.在详细讲解Kruskal最小生成树算法之前,让我们先回顾一下什么是最小生成树. 我们有一个带权值的图,我们要求找到一个所有生成树中具有最小权值的生成树.如下图所示,T是图G的生成树.但不是具有最小权值的生成树. 我们可以把他们想象成一组岛屿和连接它们的可能的桥梁.当然修桥是非常昂贵和费时的,所以我们必须要知道建设什么样的桥梁去连接各个岛.不过有一个重要的问题,建设这样一组连接所有岛屿的桥梁的最低价

最小生成树算法:Kruskal算法的Java实现

闲来无事,写个算法,最小生成树的Kruskal算法,相对比Prim算法实现起来麻烦一点点 package trees; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.PriorityQueue; import java.util.Set; /** * 最小生成树的Kruskal算法, * For a connected weighted graph G, a s

最小生成树算法

#include <stdio.h> #include <string.h> #define INFINITY 1000000 // 无穷大 #define MAX_VERTEX_COUNT 6 // 图最多顶点数 // 图的邻接矩阵 typedef int Graph[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; /*********************************************************************

算法研究:图解最小生成树之普里姆算法

我们在图的定义中说过,带有权值的图就是网结构.一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶 点,但只有足以构成一棵树的n-1条边.所谓的最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值 的和最小.综合以上两个概念,我们可以得出:构造连通网的最小代价生成树,即最小生成树(Minimum Cost Spanning Tree). 找连通图的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法,这里介绍克里姆算法. 为了能够讲明白这个算法,我们先构造网图的邻接矩

poj 3522 Slim Span:枚举+最小生成树

链接: http://poj.org/problem?id=3522 题目: Slim Span Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 4962   Accepted: 2587 Description Given an undirected weighted graph G, you should find one of spanning trees specified as follows. The grap

HDU 4081 Qin Shi Huang&#039;s National Road System (次小生成树算法)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=4081 题目: Problem Description During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China ---- they were Qi, Chu, Yan, Han, Zhao, Wei and Qin. Ying Zheng was the

UVa 10397:Connect the Campus (最小生成树)

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1338 题目: Problem E Connect the Campus Input: standard input Output: standard output Time Limit: 2 seconds Many new buildings are

UVa 10369:Arctic Network(求最小生成树的第k小边)

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1310 题目: Problem C: Arctic Network The Department of National Defence (DND) wishes to connect several northern outposts by a wir

[算法系列之三十]Dijkstra单源最短路径算法

单源最短路径问题 给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数.另外,还给定 V 中的一个顶点,称为源.现在我们要计算从源到所有其他各顶点的最短路径长度.这里的长度是指路上各边权之和.这个问题通常称为单源最短路径问题. 前面Bellman-Ford最短路径算法讲了单源最短路径的Bellman-Ford算法(动态规划算法).这里介绍另外一个更常见的算法Dijkstra算法. Dijkstra算法和 最小生成树Prim算法最小生成树算法非常类似,大家可以先熟悉下个算法.两个算法

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford