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

複制