START：
2021-08-05
15:30:20
題目鏈接：
https://www.luogu.com.cn/problem/P2330
題目詳情：
城市C是一個(gè)非常繁忙的大都市，城市中的道路十分的擁擠，于是市長(zhǎng)決定對(duì)其中的道路進(jìn)行改造。城市C的道路是這樣分布的：城市中有n個(gè)交叉路口，有些交叉路口之間有道路相連，兩個(gè)交叉路口之間最多有一條道路相連接。這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來(lái)了。每條道路都有一個(gè)分值，分值越小表示這個(gè)道路越繁忙，越需要進(jìn)行改造。但是市政府的資金有限，市長(zhǎng)希望進(jìn)行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能夠把所有的交叉路口直接或間接的連通起來(lái)。
2．在滿足要求1的情況下，改造的道路盡量少。
3．在滿足要求1、2的情況下，改造的那些道路中分值最大的道路分值盡量小。
任務(wù)：作為市規(guī)劃局的你，應(yīng)當(dāng)作出最佳的決策，選擇那些道路應(yīng)當(dāng)被修建。
輸入格式
第一行有兩個(gè)整數(shù)n,m表示城市有n個(gè)交叉路口，m條道路。
接下來(lái)m行是對(duì)每條道路的描述，u, v, c表示交叉路口u和v之間有道路相連，分值為c。(1≤n≤300，1≤c≤10000，1≤m≤100000)
輸出格式
兩個(gè)整數(shù)s, max，表示你選出了幾條道路，分值最大的那條道路的分值是多少。
輸入輸出樣例
4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8
3 6
接下來(lái)我們看題目要求：
1．改造的那些道路能夠把所有的交叉路口直接或間接的連通起來(lái)。（形成樹(shù)）
2．在滿足要求1的情況下，改造的道路盡量少。（最小生成樹(shù)）
3．在滿足要求1、2的情況下，改造的那些道路中分值最大的道路分值盡量小。（Kruskal算法按邊權(quán)重排序）
任務(wù)：作為市規(guī)劃局的你，應(yīng)當(dāng)作出最佳的決策，選擇那些道路應(yīng)當(dāng)被修建。
所以根據(jù)以上括號(hào)內(nèi)的紅體字分析，我們得使用Kruskal算法
先寫好程序的基本框架：
我們用struct結(jié)構(gòu)體來(lái)儲(chǔ)存邊的信息
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m;
struct Edge{
int u,v,w;
}edge[N];
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,w;
cin>>x>>y>>w;
edge[i]={x,y,w};
}
return 0;
}
還是老樣子（想知道以下函數(shù)請(qǐng)轉(zhuǎn)到上篇博客：http://www.rzrgm.cn/DragonMao/p/15100795.html）
寫好之后，我們可以得到一下代碼：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m;
int res=0;
int p[N];
struct Edge{
int u,v,w;
}edge[N];
bool cmp(const Edge&e1,const Edge&e2){
return e1.w<e2.w;
}
void init(){
for(int i=0;i<n;i++)p[i]=i;
}
int find(int u){
if(p[u]==u)return u;
else return p[u]=find(p[u]);
}
bool same(int u,int v){
int p1=find(u);
int p2=find(v);
if(p1!=p2){
p[p2]=p1;
return true;
}
else return false;
}
void Kruskal(){
/*
..........
*/
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,w;
cin>>x>>y>>w;
edge[i]={x,y,w};
}
init();
Kruskal();
cout<<n-1<<" "<<res<<endl;
return 0;
}
我們?cè)谳斎胪瓿芍?，我們可以看到，最短的、能夠?qū)⑺械狞c(diǎn)連接起來(lái)的最小的邊數(shù)就是n-1。所以我們可以直接輸出n-1，緊接著的res是我們經(jīng)過(guò)Kruskal函數(shù)之后，所輸出的路徑中最大權(quán)重中的最小值。
核心Kruskal函數(shù)
我們先將所有邊按權(quán)重從小到大排序，從第一條邊開(kāi)始遍歷，如果：第i條邊的兩個(gè)點(diǎn)不在一個(gè)連通塊，那么將這條邊加入連通塊，res=max(res,這條邊的權(quán)重)
void Kruskal(){
sort(edge,edge+m,cmp);
for(int i=0;i<m;i++){
if(same(edge[i].u,edge[i].v)){
res=max(res,edge[i].w);
}
}
}
完整代碼：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m;
int res=0;
int p[N];
struct Edge{
int u,v,w;
}edge[N];
bool cmp(const Edge&e1,const Edge&e2){
return e1.w<e2.w;
}
void init(){
for(int i=0;i<n;i++)p[i]=i;
}
int find(int u){
if(p[u]==u)return u;
else return p[u]=find(p[u]);
}
bool same(int u,int v){
int p1=find(u);
int p2=find(v);
if(p1!=p2){
p[p2]=p1;
return true;
}
else return false;
}
void Kruskal(){
sort(edge,edge+m,cmp);
for(int i=0;i<m;i++){
if(same(edge[i].u,edge[i].v)){
res=max(res,edge[i].w);
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,w;
cin>>x>>y>>w;
edge[i]={x,y,w};
}
init();
Kruskal();
cout<<n-1<<" "<<res<<endl;
return 0;
}
END:
2021-08-05
16:36:05
浙公網(wǎng)安備 33010602011771號(hào)