最大的可行的起重机重量
概述
二分搜索 + 并查集
https://blog.csdn.net/weixin_51650301/article/details/123603551
贪心
没有通过全部用例。
#include <bits/stdc++.h>
using namespace std;
int helper(int srcIdx, vector<vector<array<int, 2>>> &graph) {
int n = graph.size();
vector<int> maxW(n);
vector<bool> fixed(n);
int ans = INT_MAX;
maxW[srcIdx] = INT_MAX;
fixed[srcIdx] = true;
int fixedNum = 1;
int lastFixedIdx = srcIdx;
while (true) {
int nextFixedIdx = -1;
for (int i = 0; i < graph[lastFixedIdx].size(); i ++) {
int toIdx = graph[lastFixedIdx][i][0];
int toW = graph[lastFixedIdx][i][1];
if (fixed[toIdx]) continue;
maxW[toIdx] = max(maxW[toIdx], min(maxW[lastFixedIdx], toW));
if (nextFixedIdx == -1) {
nextFixedIdx = toIdx;
} else {
if (maxW[toIdx] > maxW[nextFixedIdx]) {
nextFixedIdx = toIdx;
}
}
}
if (nextFixedIdx == -1) break;
lastFixedIdx = nextFixedIdx;
fixed[nextFixedIdx] = true;
fixedNum ++;
ans = min(ans, maxW[nextFixedIdx]);
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<array<int, 2>>> graph(n);
for (int i = 0; i < m; i++) {
int u, v, p;
cin >> u >> v >> p;
graph[u - 1].push_back({ v - 1, p});
graph[v - 1].push_back({ u - 1, p});
}
// for (int i = 0; i < n; i ++) {
// sort(graph[i].rbegin(), graph[i].rend());
// }
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
ans = min(ans, helper(i, graph));
}
// ans = helper(0, graph);
cout << ans;
}
Links: 最大的可行的起重机重量