UVA10600 ACM Contest and Blackout

Graph, MST

출처: UVA UVA10600 ACM Contest and Blackout


SOL) MST와 MSP를 제외한 2번째 Spanning tree를 구하는 것.
MST의 간선 중 하나를 제외시켜 구한 Spanning tree를 구한 놈들 중 최소가
두번째 MST이다.


[-] Collapse

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

struct Union_Find{
    int component;
    vector<int> parent, rank;
    Union_Find(int n) : parent(n), rank(n), component(n-1){
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int u){
        if (parent[u] == u) return u;
        return find(parent[u]);
    }
    bool merge(int u, int v){
        u = find(u), v = find(v);
        if (parent[u] == parent[v]) return false;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) rank[v]++;
        component--;
        return true;
    }
};

Union_Find uf(0), suf(0);
int vertexNum, edgeNum;
int S1, S2;
bool used[301];
struct Edge{
    int u, v;
    int cost;
}edge[301];
void init(){
    uf = Union_Find(vertexNum + 1);
    memset(used, false, sizeof(used));
    S1 = 0;
    S2 = 1234567890;
}
bool comp(Edge l, Edge r){
    return l.cost < r.cost;
}
int subKruskal(){
    int idx = 0;
    int val = 0;
    int component = vertexNum;
    while (suf.component > 1){
        idx++;
        if (!used[idx] && suf.find(edge[idx].u) != suf.find(edge[idx].v)){
            suf.merge(edge[idx].u, edge[idx].v);
            val += edge[idx].cost;
        }
    }
    return val;
}
int main(){
    //freopen("input.txt", "r", stdin);
    int testCase;
    scanf("%d", &testCase);
    while (testCase--){
        scanf("%d%d", &vertexNum, &edgeNum);
        init();
        int u, v, cost;
        for (int i = 1; i <= edgeNum; i++){
            scanf("%d%d%d", &u, &v, &cost);
            edge[i].u = u;
            edge[i].v = v;
            edge[i].cost = cost;
        }
        sort(edge + 1, edge + edgeNum + 1, comp);
        int idx = 0;
        while (uf.component > 1){
            idx++;
            if (uf.find(edge[idx].u) != uf.find(edge[idx].v)){
                uf.merge(edge[idx].u, edge[idx].v);
                S1 += edge[idx].cost;
                used[idx] = true;
                suf = Union_Find(vertexNum + 1);
                int val = subKruskal();
                if (val < S2)
                    S2 = val;
                used[idx] = false;
            }
        }
        printf("%d %d\n", S1, S2);
    }
}