poj - 1258 Agri-Net (最小生成树)

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

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

FJ为了竞选市长，承诺为这个地区的所有农场联网，为了减少花费，希望所需光纤越少越好，给定每两个农场的花费，求出最小花费。

最小生成树。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int INF =1<<29;
int cost[maxn][maxn];
int mincost[maxn];
bool used[maxn];
int n;

int prim()
{
    for(int i=0;i<n;++i)
    {
        mincost[i]=INF;
        used[i]=false;
    }
    mincost[0]=0;
    int res=0;

    while(true)
    {
        int v=-1;
        for(int u=0;u<n;u++)
        {
            if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;
        }
        if(v==-1) break;
        used[v]=true;
        res+=mincost[v];
        for(int u=0;u<n;u++) mincost[u]=min(mincost[u],cost[v][u]);
    }
    return res;
}

int main()
{
    //freopen("a.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
            {
                scanf("%d",&cost[i][j]);
            }
        printf("%d\n",prim());
    }
    return 0;
}

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： class style log http si it la sp Go class style log http si it la sp Go

相关文章

随机文章

您可能还喜欢

您可能还喜欢