首页 > 滴滴09.13笔试第二题 城市间建立桥梁问题
头像
kill_LB
编辑于 2020-09-13 21:52
+ 关注

滴滴09.13笔试第二题 城市间建立桥梁问题

题目描述:D群岛由n个小岛组成,启动造桥工程,将n个岛连接起来。(感觉题目有问题,只要连通就可以,没有体现最小费用,该题目为无向图的联通问题)
输入描述:
测试用例组数:T
岛数,桥的方案数(i岛,j岛,费用),每座桥的成本阈值
2
3 3 400
1 2 200
1 3 300
2 3 500
3 3 400
1 2 500
1 3 600
2 3 700
解答:
不满足费用的桥的方案不参与计算即可
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1010;
const int MAX_LEN = 1010;

int connections[MAX_LEN][3];

struct cmp
{
bool operator()(const pair<int,int>& a, const pair<int,int>& b) const
{
return a.second > b.second;//小顶堆, 距离小的优先
}
};

int miniumCost(int n){
vector<bool> visited(n+1, false);
vector<vector<pair<int, int>>> edges(n+1);
for(int i = 0; i < n; ++i){
//无向图添加两次
edges[connections[i][0]].push_back({connections[i][1], connections[i][2]});
edges[connections[i][1]].push_back({connections[i][0], connections[i][2]});
}
//小顶堆
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
for(const auto &v : edges[1])   q.push({v});//从第一个顶点1开始加(随便取都可以)
visited[1] = true;
int res = 0, edge_cnt = 0;
while(!q.empty()){
int cur = q.top().first;
int dis = q.top().second;
q.pop();
if(!visited[cur]){//没有被访问过
visited[cur] = true;
res += dis;
++edge_cnt;//边数+1
if(edge_cnt == n-1) return res;
for(const auto &v : edges[cur]){
q.push(v);
}
}
}
return -1;
}
int main(){
int n, m,k,T;//分别代表顶点个数与边数
int a,b,c,num=0,index=0;
int ru[10000];
cin >>T;
//对于无向图,至少需要n-1条边才可以使得图连通
//对于有向图,至少需要n条边才可以使得图连通
while(T--){
cin>>n>>m>>k;
num=0;
while(m--){
cin>>a>>b>>c;
if(c<=k){
num++;
ru[index++]=a;
ru[index++]=b;
ru[index++]=c;
}
}
index=0;
for(int i = 0; i < num; ++i){
for(int j = 0; j < 3; ++j)
connections[i][j]=ru[index++];
}
if(num<n-1){
cout<<"No"<<endl;
}

else{
if(miniumCost(n)==-1)
cout<<"No";
else
cout<<"Yes"<<endl;
}
//cout << miniumCost(n) << endl;
}

return 0;
}


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐