时间限制: 1000 ms 内存限制: 65536 KB
提交数: 5907 通过数: 2238
【题目描述】
有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少?

【输入】
n(城市数,1<≤n≤100)

e(边数)

以下e行,每行3个数i,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 <iostream>
#include <cstring>
#include <algorithm>
#define N 128
using namespace std;

int n,m;

struct Edge
{
    int from,to,dis;
}    edge[N*N];

struct Edge_rode
{
    int from,to,dis;
    inline void operator= (const Edge &a)
    {
        dis=a.dis;
        from=min(a.from,a.to);
        to=max(a.from,a.to);
    }
}    rode[N*N];

int rode_top;

inline bool operator< (const Edge &a,const Edge &b)
{
    return a.dis<b.dis;
}
inline bool operator< (const Edge_rode &a,const Edge_rode &b)
{
    if(a.from==b.from)
        return a.to<b.to;
    return a.from<b.from;
}


int f[N];

int gz(int k)
{
    return f[k]=
                (
                    f[k]==k
                )    ?
                        k
                    :
                        gz(f[k]);
}

inline bool merge(int a,int b)
{
    int z1=gz(a),z2=gz(b);
    if(z1!=z2)
    {
        f[z2]=z1;
        return true;
    }
    return    false;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>edge[i].from>>edge[i].to>>edge[i].dis;
    }
    sort(edge,edge+m);
    
    for(int i=1;i<=n;i++)
        f[i]=i;
    int cnt=0;
    for(int i=0;i<m;i++)
    {
        if(merge(edge[i].from,edge[i].to))
        {
            rode[rode_top++]=edge[i];
            cnt++;
        }
        if(cnt == n-1)
            break;
    }
    sort(rode,rode+rode_top);
    for(int i=0;i<rode_top;i++)
    {
        cout<<rode[i].from<<' '<<rode[i].to<<endl;
    }
    
}
Last modification:February 7th, 2021 at 05:20 pm