Uva 10600 最小&次小生成樹

John

WA原始碼：
http://pastebin.com/raw.php?i=JLrhmaj8

概念是長出MST，然後窮舉移除上面每一個邊各再做一次MST找最小值為次小聲成樹權重。

目前處於一個顯然在某處有盲點的狀態。通常這種東西只要Ctrl + A Del 重打一遍BUG就會消失但是這次突然想要花時間把它找到。

求協助？謝。

[C++] 純文本查看 復制代碼

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#define MAX 106
using namespace std;

int parentof[MAX];
int groupn;

int N, M, T;

void init(){
        for(int i = 0; i < MAX; ++i) parentof[i] = i;
}

int root(int a){
        if (parentof[a] == a) return a;
        return parentof[a] = root(parentof[a]);
}

void join(int a, int b){
        //printf(": %d %d\n", a, b);
        a = root(a);
        b = root(b);
        parentof[b] = a;
}

struct edge {
        int u;
        int v;
        int w;
};
vector<edge> data;
vector<int> D;

bool cmp(edge a, edge b){
        return a.w < b.w;
}

int MST(){
        init();
        groupn = N - 1;

        int SUM = 0;

        for(int i = 0; i < data.size(); ++i){
                if(root(data[i].u) != root(data[i].v)){
                        SUM += data[i].w;
                        D.push_back(i);
                        join(data[i].u, data[i].v);
                        groupn--;
                }
        }
        //cout << D.size() << endl;
        return SUM;
}

int MST2(int disregard){
        init();
        groupn = N - 1;

        int SUM = 0;

        for(int i = 0; i < data.size(); ++i){
                if(D[disregard] == i) continue;
                if(root(data[i].u) != root(data[i].v)){
                        SUM += data[i].w;

                        join(data[i].u, data[i].v);
                        groupn--;
                }
        }
        return SUM;
}

int main(){

        scanf("%d", &T);
        while(T--){

                scanf("%d %d", &N, &M);

                data.clear();
                D.clear();

                edge tmp;

                for(int i = 0; i < M; ++i){
                        data.push_back(tmp);
                        scanf("%d %d %d", &data[i].u, &data[i].v, &data[i].w);
                }

                sort(data.begin(), data.end(), cmp);

                int m1 = MST();
                int m2 = INT_MAX;
                //cout << D.size() << endl;
                for(int k = 0; k < D.size(); ++k){
                        //cout << k << endl;
                        m2 = min(m2, MST2(k));
                }
                printf("%d %d\n", m1, m2);
        }
        return 0;
}