C++课后习题训练记录Day148

1.练习项目 ：

问题描述

蓝桥公司招聘了一个推销员。他大部分时间都在不同的城市之间旅行。他决定买一辆新车来帮助他的工作，但他必须决定新车油箱的容量。假设这辆新车每公里耗油一升。

每个城市至少有一个加油站，推销员可以在那里给油箱加油，但城市之间的道路上没有加油站。 给出城市及其之间道路的描述，找出所需油箱的最小容量，以便推销员能够至少以一种方式在任何一对城市之间旅行。

输入格式

输入的第一行包含表示测试用例数的 T。

每个测试用例的第一行包含两个整数：N 和 M ，其中 N 为城市数量，M 为道路数量。

以下 M 行都包含三个整数：X,Y,C，其中 C 是城市 X 和城市 Y 之间的长度，单位为公里。道路可以双向使用。

题目保证每对城市之间最多有一条道路相连，并且可以使用给定的道路在任意一对城市之间旅行。

输出格式

对于每个测试用例，打印一行整数表示油箱所需的最小容量。

2.选择课程

在蓝桥云课中选择题库，选择题号3322并开始练习。

3.开始练习

（1）Kruskal算法：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=1e5+10,inf=1e9;

struct Edge{
ll x,y,c;
bool operator < (const Edge &u)const{
return c<u.c;
}
};

int pre[N],n,m;
int root(int x){return pre[x]=(pre[x]==x?x:root(pre[x]));}

int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--){
cin>>n>>m;
vector<Edge>es;
for(int i=1;i<=m;i++){
ll x,y,c;cin>>x>>y>>c;
es.push_back({x,y,c});
}

sort(es.begin(),es.end());
for(int i=1;i<=n;i++)pre[i]=i;
ll ans=0;
for(const auto&t:es){
ll x=t.x,y=t.y,c=t.c;
if(root(x)==root(y))continue;
ans=max(ans,c);
pre[root(x)]=root(y);
}
cout<<ans<<'\n';
}
return 0;
}

（2）Prim算法：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=1e5+10,inf=1e9;

struct Edge{
ll x,c;
bool operator < (const Edge &u)const{
return c>u.c;
}
};

vector<Edge>g[N];
ll d[N],n,m;

ll prim()
{
priority_queue<Edge>pq;
pq.push({1,d[1]=0});
bitset<N>vis;
ll res=0;
while(pq.size()){
int x=pq.top().x;pq.pop();
if(vis[x])continue;
vis[x]=true;
res=max(res,d[x]);
for(const auto&t:g[x]){
ll y=t.x,w=t.c;
if(w<d[y])pq.push({y,d[y]=w});
}
}
return res;
}

int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++)g[i].clear(),d[i]=inf;
for(int i=1;i<=m;i++){
ll x,y,c;cin>>x>>y>>c;
g[x].push_back({y,c});
g[y].push_back({x,c});
}

cout<<prim()<<'\n';
}
return 0;
}

（3）检验结果

对此代码进行检验，检验后无报错，提交此代码，判题结果为正确100分。

（4）练习心得：注意每段代码末尾的分号是否存在 ，如不存在则需即使补充；输入法 是否切换 为英语模式；语法是否错误。