问题 B: 道路建设 (Ver. I)

问题 B: 道路建设 (Ver. I)

题目描述

有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>
#include <string>
#include <algorithm>
#define INFINITY 999999
using namespace std;

struct Edge
{
    int start,end,weight;
};

class Graph//没有使用动态数组，待优化
{
public:
    int vexnum,lnum;
    int father[100];//暂时设为100
    Edge edge[100];//边数组
public:
    void initial()
    {
        cin >> vexnum;
        lnum=0;
        for(int i=1;i<=vexnum;i++){//读入数据，初始化边数组
            for(int j=1;j<=vexnum;j++){
                int temp;
                cin >> temp;
                if(i<j){
                    edge[lnum].start=i;
                    edge[lnum].end=j;
                    edge[lnum].weight=temp;
                    lnum++;
                }
            }
        }
        for(int i=1;i<=vexnum;i++)//初始化并查集
            father[i]=i;
        int road;
        cin >> road;
        for(int i=0;i<road;i++){//先将已有的道路并查
            int t1,t2;
            cin >> t1 >> t2;
            father[t1]=t2;
        }
    }
    int find(int a)
    {
        if(father[a]!=a)return find(father[a]);
        else return a;
    }
    void sort()//边数组从0开始
    {
        for(int i=lnum-1;i>=1;i--){
            for(int j=1;j<=i;j++){
                if(edge[j-1].weight>edge[j].weight){
                    Edge temp=edge[j-1];
                    edge[j-1]=edge[j];
                    edge[j]=temp;
                }
            }
        } 
    }
    int kruskal()
    {
        int k=0;//计数
        int value=0;
        for(int i=0;i<lnum-1;i++){//lnum-1条边
            if(k>=vexnum-1)break;
            int t1=edge[i].start;
            int t2=edge[i].end;
            int a1=find(t1);
            int a2=find(t2);
            if(a1!=a2){
                father[a1]=a2;
                value+=edge[i].weight;
                k++;
            }
        }
        return value;
    }
};

int main()
{
    Graph graph;
    graph.initial();
    graph.sort();
    cout << graph.kruskal();
    return 0;
}

目的

一个笔记