08-图7 公路村村通 (30分)

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数NN（\le 1000≤1000）和候选道路数目MM（\le 3N≤3N）；随后的MM行对应MM条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到NN编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出-1−1，表示需要建设更多公路。

输入样例:

6 15

1 2 5

1 3 3

1 4 7

1 5 4

1 6 2

2 3 4

2 4 6

2 5 2

2 6 6

3 4 6

3 5 1

3 6 1

4 5 10

4 6 8

5 6 3

输出样例:

12

#include <iostream>
#include <cstring>
#include <vector>
#define INF 1 << 30 
#define N 1002
using namespace std;

struct Edge{
    int v1;
    int v2;
    int weight;
};

class Graph{
    private:
        int** G;
        int nv;                         //结点个数 
        int* dist;                      //距离数组 
        int* parent;                    //父节点下标数组 
        vector<struct Edge> MST;         
    public:
        Graph(int nv,int ne){
            this->nv = nv;
            this->G = new int*[N];
            this->dist = new int[N];
            this->parent = new int[N];
            memset(this->parent,0,sizeof(int)*N);
            for ( int i = 0 ; i < N ; i++){
                this->G[i] = new int[N];
                memset(this->G[i],0,sizeof(int)*N);
                this->G[i][i] = 0;
            }

            for ( int i = 0 ; i < ne ; i++){
                int a,b,c;
                cin>>a>>b>>c;
                this->G[a-1][b-1] =c;
                this->G[b-1][a-1] =c;
            }
        }

        int FindMinDist(){
            int mindist = INF;
            int minindex = 0;
            for ( int i = 0 ; i < this->nv ; i++){
                if ( this->dist[i] != 0&&this->dist[i] < mindist){
                    mindist = this->dist[i];
                    minindex = i;
                }
            } 

            if ( mindist < INF){
                return minindex;
            }else{
                return -1;
            }
        }

        int Prime(){
            int cnt = 0;
            int total_sum = 0;
            this->dist[0] = 0;
            this->parent[0] = -1;
            struct Edge edge;

            for (int i = 0 ; i < this->nv ; i++){
                this->dist[i] = this->G[0][i];
                this->parent[i] = 0;
            }
            cnt++;
            this->parent[0] = -1; 

            while(1){
                int V = this->FindMinDist();
                if ( V == -1){
                    break;
                }

                edge.v1 = this->parent[V];
                edge.v2 = V;
                edge.weight = this->dist[V];
                MST.push_back(edge);
                total_sum += this->dist[V];
                this->dist[V] = 0;
                cnt++;

                for ( int i = 0 ; i < this->nv ; i++){
                    if ( this->dist[i] != 0 && this->G[V][i] < INF){
                        if ( this->G[V][i] < this->dist[i]){
                            this->dist[i] = this->G[V][i];
                            this->parent[i] = V;
                        }
                    }
                } 
            }
            if ( cnt < this->nv){
                total_sum = -1;
            }
            return total_sum;
        }

        void Print(){
            for ( int i = 0 ; i < this->nv ; i++){
                for ( int j = 0 ; j < this->nv ; j++){
                    cout<<this->G[i][j]<<" "; 
                }
                cout<<endl;
            }
        }
};

int main()
{
    int city_num,road_num;
    cin>>city_num>>road_num;

    Graph graph(city_num,road_num);
    //graph.Print();
    int sum = graph.Prime();
    cout<<sum;

    return 0;
 }             

复制