vijos-1045.cpp

/*
    Luna Capsule / vijos-1045

    Problem: https://vijos.org/p/1045
    Record: https://vijos.org/records/54413c5817f3ca0e15b0a872

    - 一道裸MST(最小生成樹)的題目
      Kruskal+路徑壓縮的並查集即可被Accepted, #8與#9測試點需要特別注意 (见代码注释)
*/

#include <algorithm>
#include <cstdio>

using namespace std;

const unsigned MAXNODE = 100001;
const unsigned MAXEDGE = 100001;

struct EDGE { unsigned a, b; double l; } e[MAXEDGE];
unsigned p[MAXEDGE], n, m;
double s;

unsigned us[MAXNODE];

bool cmp(unsigned x, unsigned y) { return e[x].l < e[y].l; }

void init() {
    unsigned i = 0;

    scanf("%lf", &s);
    scanf("%d", &n);
    while (scanf("%d %d %lf", &e[i].a, &e[i].b, &e[i].l) != EOF)
        p[i] = i, i++;
    sort(p, p + i, cmp), m = i; // Kruskal: 對邊按長度排序
}

inline unsigned queryRoot(unsigned a) { unsigned i; i = a; while (us[i] != 0) i = us[i]; return i; }

void process() {
    unsigned i, nodes = 0, rx, ry;
    double ans = 0;

    /* 不斷按長度遞增(貪心地)檢查是否能加入樹中 */
    for (i = 0; i < m; i++)
        if (nodes < n) { // 當加入足夠的邊能構成一顆完整的MST即可結束
            rx = queryRoot(e[p[i]].a);
            ry = queryRoot(e[p[i]].b);

            /* 帶簡單路徑壓縮的並查集合併 */
            if (rx == 0)
                if (ry == 0)
                    us[e[p[i]].a] = e[p[i]].b;
                else
                    us[e[p[i]].a] = ry;
            else
                if (ry == 0)
                    us[e[p[i]].b] = rx;
                else
                    if (rx != ry)
                        us[rx] = us[e[p[i]].a] = ry;
                    else
                        continue;
            nodes++, ans += e[p[i]].l;
        } else
            break;

    if (nodes == (n - 1))
        if (ans <= s)
            printf("Need %.2lf miles of cable", ans);
        else
            printf("Impossible"); // 這是第9個測試點, 需要注意判定總長是否滿足要求
    else
        printf("Impossible"); // 這是第10測試點, 需要判定圖是否連通圖
}

int main() {
    init();
    process();
}

/*
    COMMIT LOG

    #1: 未加入總長判定
        测试数据 #8: WrongAnswer, time = 203 ms, mem = 2484 KiB, score = 0
        测试数据 #9: WrongAnswer, time = 11 ms, mem = 2480 KiB, score = 0

        WrongAnswer, time = 1839 ms, mem = 2488 KiB, score = 80

    #2: 未加入連通圖判定
        测试数据 #9: WrongAnswer, time = 0 ms, mem = 2484 KiB, score = 0

        WrongAnswer, time = 1199 ms, mem = 2488 KiB, score = 90

    #3: Accepted
        测试数据 #0: Accepted, time = 109 ms, mem = 2600 KiB, score = 10
        测试数据 #1: Accepted, time = 46 ms, mem = 2596 KiB, score = 10
        测试数据 #2: Accepted, time = 234 ms, mem = 2596 KiB, score = 10
        测试数据 #3: Accepted, time = 187 ms, mem = 2600 KiB, score = 10
        测试数据 #4: Accepted, time = 218 ms, mem = 2596 KiB, score = 10
        测试数据 #5: Accepted, time = 234 ms, mem = 2596 KiB, score = 10
        测试数据 #6: Accepted, time = 234 ms, mem = 2596 KiB, score = 10
        测试数据 #7: Accepted, time = 280 ms, mem = 2596 KiB, score = 10
        测试数据 #8: Accepted, time = 265 ms, mem = 2600 KiB, score = 10
        测试数据 #9: Accepted, time = 0 ms, mem = 2600 KiB, score = 10

        Accepted, time = 1807 ms, mem = 2600 KiB, score = 100

    #4: Accepted (追加當構成一顆完整MST時退出的判定)
        测试数据 #0: Accepted, time = 109 ms, mem = 2600 KiB, score = 10
        测试数据 #1: Accepted, time = 46 ms, mem = 2596 KiB, score = 10
        测试数据 #2: Accepted, time = 234 ms, mem = 2596 KiB, score = 10
        测试数据 #3: Accepted, time = 187 ms, mem = 2600 KiB, score = 10
        测试数据 #4: Accepted, time = 218 ms, mem = 2596 KiB, score = 10
        测试数据 #5: Accepted, time = 234 ms, mem = 2596 KiB, score = 10
        测试数据 #6: Accepted, time = 234 ms, mem = 2596 KiB, score = 10
        测试数据 #7: Accepted, time = 280 ms, mem = 2596 KiB, score = 10
        测试数据 #8: Accepted, time = 265 ms, mem = 2600 KiB, score = 10
        测试数据 #9: Accepted, time = 0 ms, mem = 2600 KiB, score = 10
        
        Accepted, time = 1807 ms, mem = 2600 KiB, score = 100
*/