随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.1.1 Agri-Net (最小生成树)

标准的最小生成树问题. Prim, kruskal 均可.

/*
ID: lorelei3
TASK: agrinet
LANG: C++
*/

#include <fstream>
#include <iostream>

using namespace std;

const int MAX = 105;
const int INF = 100000000;

int g[MAX][MAX];
int lowcost[MAX], s[MAX]; 
int ans, n;

void prim(int n){
    int i,j,k,min;
    ans = 0;

    for(i=1; i<n; ++i)
        lowcost[i] = g[0][i];

    s[0]=1;

    for(i=0; i<n-1; ++i){
        min = INF;
        j=0;

        for(k=1; k<n; ++k)
            if(!s[k]&&lowcost[k]<min){
                min=lowcost[k];
                j=k;
            }

        ans+=min;
        s[j]=1;

        for(k=1; k<n; ++k)
            if(!s[k] && j!=k && g[j][k]<lowcost[k])
                lowcost[k]= g[j][k];
    }
}

int main(){
    int i,j;

    ifstream fin("agrinet.in");
    ofstream fout("agrinet.out");

    fin>>n;

    for(i=0; i<n; ++i){
        lowcost[i] = INF;
        s[i]=0;
    }

    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            fin>>g[i][j];

    prim(n);

    fout<<ans<<endl;
    return 0;
}
posted on 2010-12-14 16:49 小阮 阅读(397) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮