滴滴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;
}