问题 B: 【例4-9】城市公交网建设问题

问题 B: 【例4-9】城市公交网建设问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 135  解决: 70
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1711&pid=1

题目描述

有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？

输入

n（城市数，1<≤n≤100）

e（边数）

以下e行，每行3个数i,j,wiji,j,wij ，表示在城市i,j之间修建高速公路的造价。

输出

n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。

注意看测试数据的输出顺序，有排序要求。

样例输入

5 8

1 2 2

2 5 9

5 4 7

4 1 10

1 3 12

4 3 6

5 3 3

2 3 8

样例输出

1 2

2 3

3 4

3 5

思路：最小生成树，用克鲁斯卡尔解决，然后按字典序列输出就行了

代码：

#include<bits/stdc++.h>

using namespace std;

int n, m;

struct Node

{

    int first, end, c;

}edge[100000];

int father[100000];

bool cmp(const Node a, const Node b)//对边排序

{

    return a.c < b.c;

}

void init()//初始化父节点

{

    for (int i = 1; i <= m; i++)

    {

         father[i] = i;

    }

}

int Find(int a)

{

    return father[a] == a ? a : father[a] = Find(father[a]);//寻找父节点

}

struct aa

{

    int xx, yy;

}s[10000];

bool cmp1(const aa a, const aa b)

{

    if (a.xx == b.xx)return a.yy < b.yy;

    return a.xx < b.xx;

}

int main()

{

    int ans = 0;

    cin >> n;

    cin >> m;

    int num = 0;

    int sum = 0;

    for (int i = 1; i <= m; i++)//克鲁斯卡尔算法

    {

         cin >> edge[i].first >> edge[i].end >> edge[i].c;

         sum += edge[i].c;

    }

    init();

    sort(edge + 1, edge + m + 1, cmp);

    for (int i = 1; i <= m; i++)

    {

         int a = Find(edge[i].first);

         int b = Find(edge[i].end);

         if (a != b)//节点覆盖

         {

             father[a] = b;

             s[++num].xx = min(edge[i].first, edge[i].end);

             s[num].yy = max(edge[i].first, edge[i].end);

             //ans+=edge[i].c;

         }



    }

    sort(s + 1, s + num + 1, cmp1);

    for (int i = 1; i <= num; i++)

    {

         cout << s[i].xx << " " << s[i].yy << endl;

    }







}