题目

问题 B: 道路建设 (Ver. I)
时间限制: 1 Sec  内存限制: 128 MB
提交: 1233  解决: 308
[提交][状态][讨论版]
题目描述
有N个村庄，编号从1到N，你应该建造一些道路，使每个村庄都可以相互连接。

两个村A和B是相连的，当且仅当A和B之间有一条道路，或者存在一个村C使得在A和C之间有一条道路，并且C和B相连。

现在一些村庄之间已经有一些道路，你的任务就是修建一些道路，使所有村庄都连通起来，并且所有道路的长度总和是最小的。
输入
测试数据有多组

第一行是整数N（3 <= N <= 100），代表村庄的数量。 然后是N行，其中第i行包含N个整数，这些N个整数中的第j个是村庄i和村庄j之间的距离（距离是[1,1000]内的整数）。

然后是整数Q（0 <= Q <= N *（N + 1）/ 2），接下来是Q行，每行包含两个整数a和b（1 <= a <b <= N），代表着村庄a和村庄b之间的道路已经建成。
输出
对于每组测试数据

输出一个整数，表示要构建的道路的长度总和最小值

样例输入
3
0 990 692
990 0 179
692 179 0
1
1 2
样例输出
179

代码块

#include <iostream>
using namespace std;

class Edge
{
    int weight, startvex, endvex;
public:
    friend class Graph;
};

class Graph
{
    int vexnum;
    int edgenum;
    int n;
    int weightsum;
    int **matrix;
    Edge *edge;
    int *parent;
    int FindRoot(int vex);
public:
    Graph();
    ~Graph();
    void Kruskal();
};

Graph::Graph()
{
    int i, j;
    weightsum = 0;
    cin>>vexnum;
    edgenum = vexnum*(vexnum-1)/2;
    matrix = new int*[vexnum];
    edge = new Edge[edgenum];
    parent = new int[vexnum];
    for(i=0; i<vexnum; i++)
    {
        matrix[i] = new int[vexnum];
        parent[i] = -1;
        for(j=0; j<vexnum; j++)
            cin>>matrix[i][j];
    }
    int num = 0;
    for(i=0; i<vexnum; i++)
    {
        for(j=i+1; j<vexnum; j++)
        {
            edge[num].startvex = i;
            edge[num].endvex = j;
            edge[num].weight = matrix[i][j];
            num++;
        }
    }
    Edge temp;
    for(i=0; i<edgenum-1; i++)
    {
        for(j=0; j<edgenum-1-i; j++)
        {
            if(edge[j].weight>edge[j+1].weight)
            {
                temp = edge[j];
                edge[j] = edge[j+1];
                edge[j+1] = temp;
            }
        }
    }
    cin>>n;
    int vex1, vex2;
    for(i=0; i<n; i++)
    {
        cin>>vex1>>vex2;
        parent[vex2-1] = vex1-1;
    }
}

Graph::~Graph()
{
    for(int i=0; i<vexnum; i++)
    {
        delete []matrix[i];
    }
    delete []matrix;
    delete []edge;
    delete []parent;
}

int Graph::FindRoot(int vex)
{
    while(parent[vex]!=-1)
        vex = parent[vex];
    return vex;
}

void Graph::Kruskal()
{
    int i, vex1, vex2;
    int num = 0;
    for(i=0; i<edgenum; i++)
    {
        vex1 = FindRoot(edge[i].startvex);
        vex2 = FindRoot(edge[i].endvex);
        if(vex1!=vex2)
        {
            weightsum += edge[i].weight;
            parent[vex2] = vex1;
            num++;
            if(num==vexnum-1-n)
            {
                cout<<weightsum<<endl;
                return;
            }
        }
    }
}

int main(void)
{
    Graph myGraph;
    myGraph.Kruskal();
    return 0;
}