Agri-Net
Time Limit: 1000MS
|
Memory Limit: 10000K
|
Total Submissions: 28121
|
Accepted: 11149
|
题目链接:http://poj.org/problem?id=1258
Description
Farmer John has been electedmayor of his town! One of his campaign promises was to bring internetconnectivity 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 sharehis connectivity with the other farmers. To minimize cost, he wants to lay theminimum 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 mustfind the minimum amount of fiber needed to connect them all together. Each farmmust connect to some other farm such that a packet can flow from any one farmto any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes severalcases. For each case, the first line contains the number of farms, N (3 <= N<= 100). The following lines contain the N x N conectivity matrix, whereeach element shows the distance from on farm to another. Logically,
they are N linesof N space-separated integers. Physically, they are limited in length to 80characters, so some lines continue onto others. Of course, the diagonal will be0, since the distance from farm i to itself is not interesting for thisproblem.
Output
For each case, output a singleinteger length that is the sum of the minimum length of fiber required toconnect the entire set of farms.
Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
Source
USACO102
解题思路:
给你一张图,求最短路径,这是一到典型的求最短路径模版体,用prim()算法就能过。
代码:
#include <iostream>
#include<cstdio>
#include<cstring>
#define MAX 103
#define VALUE 0xfffff
using namespace std;
int g[MAX][MAX];
int visited[MAX];
int minCost[MAX];
int prim(int n)
{
int i;
for(i=0;i<n;i++)
{
visited[i]=0;
minCost[i]=VALUE;
}
minCost[0]=0;
int res=0;
while(true)
{
int t=-1;
for(i=0;i<n;i++)
{
if(visited[i]==0 && (t==-1 || minCost[i]<minCost[t]))
{
t=i;
}
}
if(t==-1)
break;
visited[t]=1;
res+=minCost[t];
for(i=0;i<n;i++)
{
if(minCost[i]>g[i][t] && g[i][t]!=0)
{
minCost[i]=g[i][t];
}
}
}
return res;
}
int main()
{
int i,j;
int n;
while(scanf("%d",&n)!=EOF)
{
memset(g,0,sizeof(g));
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&g[i][j]);
}
}
printf("%d\n",prim(n));
}
return 0;
}
分享到:
相关推荐
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
POJ水题集-----50道左右-----增加自信啊..
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
poj 1699的代码和方法说明,个人原创
poj题目分类--acmer做题极有用资源
C_(POJ_1854)(分治).cpp
北大POJ1002-487-3279【Hash+Qsort】 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
经典的状态DP难题,非常好的的题目,我做了很久才做出来,强烈推荐!!1
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
Time Limit: 1000ms Memory limit: 65536kB 题目描述 有9个时钟,排成一个3*3的矩阵。 现在需要用最少的移动,将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示,每个移动会将若干个时钟的...
poj 3131 Cubic Eight-Puzzle.md