Description
城市C是一個非常繁忙的大都市，城市中的道路十分的擁擠，于是市長決定對其中的道路進行改造，城市C的道路是這樣分布的：城市中有n個交叉路口，有些交叉路口之間有道路相連，兩個交叉路口之間最多有一條道路相連接，這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來了，每條道路都有一個分值，分值越小表示這個道路越繁忙，越需要進行改造，但是市政府的資金有限，市長希望進行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能夠把所有的交叉路口直接或間接的連通起來，
2．在滿足要求1的情況下，改造的道路盡量少，
3．在滿足要求1、2的情況下，改造的那些道路中分值最大的道路分值盡量小，
任務：作為市規劃局的你，應當作出最佳的決策，選擇那些道路應當被修建，
Input
第一行有兩個整數n,m表示城市有n個交叉路口，m條道路，
接下來m行是對每條道路的描述，u,v,c表示交叉路口u和v之間有道路相連，分值為c，
Output
兩個整數s,max，表示你選出了幾條道路，分值最大的那條道路的分值是多少，
Sample Input 1
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
Sample Output 1
3 6
Hint
(1≤n≤300，1≤c≤10000，1≤m≤100000)
分析：一看題目的“把所有交叉路口連通起來”、“改造道路盡量少”、“改造道路中分值最大的道路分值盡量小”，可知這符合最小生成樹的定義，這道題就是最小生成樹裸題，
AC代碼：
#include <stdio.h>
#include <algorithm>
#include <string.h>
struct EDGE//存邊
{
int u;//端點1
int v;//端點2
int val;//邊權
friend bool operator<(EDGE &edge1,EDGE &edge2)//排序規則
{
return edge1.val<edge2.val;
}
}edge[100010];
int n,m;//點數，邊數
int ans;//記錄最小生成樹的最大邊邊權
int cnt=0;//記錄當前已選多少條邊
int parent[310];//記錄父節點
int rank[310];//記錄樹層數，只有一個節點算0層
inline void initialise()//初始化
{
for(int i=1;i<=n;++i)
{
parent[i]=i;//開始時每個端點都是獨立的，自己是自己父節點
}
memset(rank,0,sizeof(rank));//開始時都是0層
}
int find_root(int x)//尋找根節點
{
int x_root=x;
while(parent[x_root]!=x_root)
{
x_root=parent[x_root];
}
return x_root;
}
int union_vertices(int x,int y)//合并兩個節點到一個集合
{
int x_root=find_root(x);
int y_root=find_root(y);
if(x_root==y_root){//合并將產生環，不能合并
return 0;
}
else {
//合并時進行路徑壓縮，層數小的樹合并到層數大的樹上不增加其層數
//兩棵層數相等的樹合并，層數增1
if(rank[x_root]>rank[y_root])
{
parent[y_root]=x_root;
}
else if(rank[x_root]<rank[y_root])
{
parent[x_root]=y_root;
}
else {
parent[x_root]=y_root;
++rank[y_root];
}
return 1;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val);
}
std::sort(edge,edge+m);//給邊排序
initialise();
for(int i=0;i<m;++i)//從最小邊開始挑選，成環則不選
{
if(union_vertices(edge[i].u,edge[i].v))
{
++cnt;
ans=edge[i].val;
if(cnt==n-1) break;
}
}
printf("%d %d",n-1,ans);//列印答案
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/44660.html
標籤：其他
上一篇：面試題精選:資料偽造
下一篇：【Godot】制作技能節點