城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。
任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
大意就是用最小的代价把N个点的图变成连通图（要求1、2）
那么，N个点的联通图最小需要N-1条边，这显然是一个MST的题。
根据要求3，显然使用并查集维护的Kruskal更优。
那这就是个MST的裸题了……QnQ这么简单为什么还要发题解
关于s，可以知道它肯定是N-1 （N是点数）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#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; } |