趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
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;
}
|