제출 #1244203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244203		yue_lai	시간이 돈 (balkan11_timeismoney)	C++20	100 / 100	438 ms	1764 KiB

timeismoney

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// 邊的結構，增加了 id 來記錄原始索引
struct Edge {
    int u, v, t, c;
    int id; 
    long double weight; // 使用浮點數來計算加權後的權重
};

// 代表一個解 (一棵生成樹) 的結構
struct Solution {
    long long time;
    long long money;
    vector<int> edge_ids; // 記錄構成此樹的邊的 ID

    // 用於比較兩個解是否相同
    bool operator==(const Solution& other) const {
        return time == other.time && money == other.money;
    }
};

int n;
vector<Edge> initial_edges;
vector<int> parent;
vector<Solution> hull_points; // 儲存所有凸包上的點

int find_set(int i) {
    if (parent[i] == i) return i;
    return parent[i] = find_set(parent[i]);
}

// Kruskal 演算法，根據指定的 k 值計算 MST
Solution kruskal(long double k) {
    for (auto& edge : initial_edges) {
        // 核心：根據 k 值計算新的權重
        edge.weight = k * edge.t + edge.c;
    }

    sort(initial_edges.begin(), initial_edges.end(), [](const Edge& a, const Edge& b) {
        // 權重相同時，優先選 t*c 較小的 (可選，一種穩定排序策略)
        if (a.weight == b.weight) {
            return (long long)a.t * a.c < (long long)b.t * b.c;
        }
        return a.weight < b.weight;
    });

    parent.assign(n, 0);
    for (int i = 0; i < n; ++i) parent[i] = i;

    Solution sol = {0, 0};
    int edges_count = 0;

    for (const auto& edge : initial_edges) {
        int root_u = find_set(edge.u);
        int root_v = find_set(edge.v);
        if (root_u != root_v) {
            parent[root_v] = root_u;
            sol.time += edge.t;
            sol.money += edge.c;
            sol.edge_ids.push_back(edge.id); // 記錄邊的原始 ID
            edges_count++;
            if (edges_count == n - 1) break;
        }
    }
    return sol;
}

// 遞迴函式，尋找凸包頂點
void find_hull(const Solution& p1, const Solution& p2) {
    long double k = 0;
    // 防止除以零
    if (p2.time - p1.time != 0) {
        k = -(long double)(p2.money - p1.money) / (p2.time - p1.time);
    } else {
        // 如果時間相同，斜率為無窮大，對應 k 也為極大值
        // 我們要找的是最小化 time 的點，這裡傳入極大 k 即可模擬
         k = LLONG_MAX;
    }

    Solution p3 = kruskal(k);

    // 判斷點 p3 是否在 p1 和 p2 構成的線段之外
    // 透過叉積判斷，如果叉積 > 0，則 p3 在線段下方，是新的凸包點
    // (p2-p1) x (p3-p1) > 0
    // (p2.t-p1.t)*(p3.m-p1.m) - (p2.m-p1.m)*(p3.t-p1.t) > 0
    long double cross_product = (long double)(p2.time - p1.time) * (p3.money - p1.money) - (long double)(p2.money - p1.money) * (p3.time - p1.time);
    
    // 考慮浮點數誤差，用一個很小的 epsilon
    if (cross_product > 1e-9) {
        find_hull(p1, p3);
        hull_points.push_back(p3);
        find_hull(p3, p2);
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    while (cin >> n >> m) {
        initial_edges.clear();
        hull_points.clear();
        vector<Edge> original_input_edges; // 為了最後輸出用

        for (int i = 0; i < m; ++i) {
            int u, v, t, c;
            cin >> u >> v >> t >> c;
            initial_edges.push_back({u, v, t, c, i});
        }
        original_input_edges = initial_edges;

        Solution p_min_money = kruskal(0);
        Solution p_min_time = kruskal(LLONG_MAX);
        
        hull_points.push_back(p_min_money);
        if (!(p_min_time == p_min_money)) {
            find_hull(p_min_money, p_min_time);
            hull_points.push_back(p_min_time);
        }
        
        long double min_product = -1;
        Solution best_solution;

        for (const auto& sol : hull_points) {
            long double product = (long double)sol.time * sol.money;
            if (min_product < 0 || product < min_product) {
                min_product = product;
                best_solution = sol;
            }
        }
        
        // --- 輸出部分 ---
        cout << best_solution.time << " " << best_solution.money << "\n";
        for (int edge_id : best_solution.edge_ids) {
            // edge_id 就是原始邊在 original_input_edges 中的索引
            const Edge& edge_to_print = original_input_edges[edge_id];
            cout << edge_to_print.u << " " << edge_to_print.v << "\n";
        }
    }

    return 0;
}

• Subtask 1: 100 / 100