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

[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;
}