最大的可行的起重机重量

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-21 17:44:43
    编辑于：2022-03-22 21:42:35
    浏览量：522

概述

二分搜索 + 并查集

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: 最大的可行的起重机重量