用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

畅通工程之最低成本建设问题

2017-11-17 作者:芙蓉妹妹举报

[c++]代码库

#include<bits/stdc++.h>
using namespace std;
int M[1002][1002], Dist[1002], TF[1002];
void tree(int N)
{
    int k, sum=0 ,i ,j;
    for ( i = 2; i <= N; i ++)//把所有与顶点1相邻的边放入Dist数组
        Dist[i] = M[1][i];
    TF[1] = 1;
    for ( i = 0; i < N-1; i ++)
    {
        int min1 = 9999, k = -1;
        for ( j = 1; j <= N ; j ++)
        {
            if ( !TF[j] && Dist[j] < min1)//如果当前道路未被经过且权值小于当前最小的权值
            {
                min1 = Dist[j];//更改最小权值数值
                k = j;//记录最小全职的下标
            }
        }
        if ( k == -1 )//如果K的下标还是-1,说明没有通向该村庄的道路
        {
            cout<<"Impossible"<<endl;
            return ;
        }
        TF[k] = 1;//记录该条道路已经过
        sum += min1;
        for ( j = 1; j <= N; j ++)
        {
            if ( !TF[j] && M[k][j] < Dist[j] )
                Dist[j]=M[k][j];
        }
    }
    cout<<sum<<endl;
}
int main()
{
    int N, m, i, j;
    while(cin>>N>>m)
    {
        for ( i = 1 ;i <= N ; i ++)
        {
            Dist[i] = 9999;
            TF[i] = 0;//所有道路都标志为未经过
            for ( j = 1; j <= N ; j ++)
                M[i][j] = 9999;//所有道路权值初始化为无穷大
        }
        for ( i = 0 ; i < m ; i ++)//输入有权无向图的邻接矩阵
        {
            int a, b, c;
            cin>>a>>b>>c;
            M[a][b] = c;
            M[b][a] = c;
        }
        tree(N);
    }
    return 0;
}


分享到:
更多

网友评论    (发表评论)

共1 条评论 1/1页

发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。