POJ 1258 Agri-Net

浏览数：34 / 时间：2015年06月09日

题目链接

http://poj.org/problem?id=1258

题目大意：

农民约翰竞选为了这个小镇的市长，他竞选的时候承诺要把他所管辖区域的所有地方的网络连接起来。当然他需要你的帮助，约翰需要一个可以快速到达所有农民的联通网，为了降低成本他想要最少的光纤来来连接其他的农场。

给你一个表，代表从一个农场到达另一个农场所需要的光纤花费，你要找出将所有农场连接起来的最小花费。每个农场都要连接起来，我从一个农场可以到达其他任何一个农场，这里农场之间的距离不会超过 100000.

输入：

输入包含多个测试实例，第一个一个 N 代表有N 个城镇，然后是个 N*N 的邻接矩阵，

输出：

输出最小生成树。

题目分析：

明显的是求一个最小生成树，因为下面给的就是邻接矩阵，所以我们用邻接矩阵写是最好不过了，直接 Prime+ 邻接矩阵搞定

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
#define maxn 103

struct Edge
{
    int e, w;
    Edge(int e=0,int w=0) : e(e), w(w) {}
};

int G[maxn][maxn];
bool vis[maxn];
int dist[maxn], n;
int Prime()
{
    int sum = 0;
    dist[0] = 0;
    for(int i=0; i<n; i++)
    {
        int Min = INF, index;
        for(int j=0; j<n; j++)
        {
            if(!vis[j] && Min > dist[j])
                index = j, Min = dist[j];
        }
        sum += Min;
        vis[index] = true;

        for(int j=0; j<n; j++)
        {
            if(!vis[j] && dist[j] > G[index][j])
            {
                dist[j] = G[index][j];
            }
        }
    }
    return sum;
}
void Init()
{
    for(int i=0; i<n; i++)
    {
        vis[i] = false;
        dist[i] = INF;
    }
}

int main()
{
    while(cin >> n)
    {
        Init();
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cin >> G[i][j];
            }
        }

        int ans = Prime();

        cout << ans <<endl;
    }
    return 0;
}