城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

大意就是用最小的代价把N个点的图变成连通图(要求1、2)

那么,N个点的联通图最小需要N-1条边,这显然是一个MST的题。

根据要求3,显然使用并查集维护的Kruskal更优。

那这就是个MST的裸题了……QnQ这么简单为什么还要发题解

关于s,可以知道它肯定是N-1 (N是点数)
 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<iterator>
using namespace std;

struct ed
{
    int from,to,w;
}edge[50010]={0};
int edgenum=0,nodenum=0;
int fatherx[1010]={0},mst=0,c1=0;

bool cmp(ed a,ed b)
{
    return a.w<b.w;
}

int findx(int e1)
{
    if (fatherx[e1]!=e1) fatherx[e1]=findx(fatherx[e1]);
    return fatherx[e1];
}

void mergex(int e1,int e2)
{
    fatherx[findx(e2)]=findx(e1);
}

int main()
{
    scanf("%d%d",&nodenum,&edgenum);
    for (int i=1;i<=edgenum;i++)
    {
        scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].w);
    }
    
    sort(edge+1,edge+1+edgenum,cmp);
    for (int i=1;i<=nodenum;i++) fatherx[i]=i;
    
    for (int i=1;i<=edgenum;i++)
    {
        if (findx(edge[i].from)!=findx(edge[i].to))
        {
            mergex(edge[i].from,edge[i].to);
            mst=edge[i].w;
            c1++;
        }
        if (c1==nodenum-1) break;
    }
    printf("%d %d\n",nodenum-1,mst);
    return 0;
}
分类: Kruskal

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.