hihoCoder 1097 : 最小生成树一·Prim算法

#1097 : 最小生成树一·Prim算法

10000ms

1000ms

256MB

描述

最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！

但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。

输入

每个测试点（输入文件）有且仅有一组测试数据。

在一组测试数据中：

第1行为1个整数N，表示小Hi拥有的城市数量。

接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。

对于100%的数据，满足N<=10^3，对于任意i，满足Aii=0，对于任意i, j满足Aij=Aji, 0<Aij<10^4.

输出

对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。

样例输入

5 0 1005 6963 392 1182 1005 0 1599 4213 1451 6963 1599 0 9780 2789 392 4213 9780 0 5236 1182 1451 2789 5236 0

样例输出

4178

//与最短路劲的Dijkstra算法 类似
//给出整个邻接矩阵 
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define N  1001
#define MAX 99999999
int map[N][N];
int dis[N],vis[N];
int n;
int prime()
{
  int i,j,loc,min;
  memset(vis,0,sizeof(vis));
  
  int ans=0;
  loc=1;
  for(i=1;i<=n;i++)
    dis[i]=map[loc][i];
  
  vis[loc]=1;
  for(i=1;i<n;i++)
  {
    min=MAX;
    loc=-1;
    for(j=1;j<=n;j++)
    {
      if(!vis[j]&&dis[j]<min)
      {
        loc=j;
        min=dis[j];
      } 
    }
    ans+=min;
    vis[loc]=1;
    for(j=1;j<=n;j++)
    {
      if(!vis[j]&&map[loc][j]<dis[j])
      {
        dis[j]=map[loc][j];
      }
    }
  }
  return ans;
} 
int main()
{
  int i,j,a;

  while(scanf("%d",&n)!=EOF)
  {
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
      {
        scanf("%d",&a);
        map[i][j]=a;
      }
    printf("%d\n",prime());
  }
  return 0;
}