查看: 693|回復: 0

[提問] Uva 10600 最小&次小生成樹

[複製鏈接]

該用戶從未簽到

2

主題

16

帖子

87

積分

高一新生

Rank: 2

積分
87

新手達陣台南一中資訊社

發表於 2014-9-6 17:41:10 | 顯示全部樓層 |閱讀模式

趕快加入我們來參與討論吧!

您需要 登錄 才可以下載或查看,沒有帳號?加入我們

x
本帖最後由 John 於 2014-9-12 17:39 編輯

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;
}


Live safe.
Die anyway.
回復

使用道具 檢舉

您需要登錄後才可以回帖 登入 | 加入我們

本版積分規則

快速回覆 返回頂部 返回列表