# 11566: 【原1566】最小生成树问题

### 题目描述

author: 孙梦璇 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1566

## Sample Input 1

``````9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
``````

## Sample Output 1

``````216
``````

## Sample Input 2

``````3
A 2 B 10 C 40
B 1 C 20
``````

## Sample Output 2

``````30
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/18.
//
//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BPRIORITYQUEUE_H
#define SBL_BPRIORITYQUEUE_H

namespace bpq {
template<typename Item>
struct greater {
bool operator()(const Item &a, const Item &b) {
return a > b;
}
};

template<typename Item>
struct less {
bool operator()(const Item &a, const Item &b) {
return a < b;
}
};
}

template<typename Item, typename Comparator = bpq::greater<Item>>
class BPriorityQueue {
Comparator comparator;
Item *pq;
int N = 0;
int maxN;
int minN;

private:
bool cmp(int i, int j) {
return comparator(pq[i], pq[j]);
}

void exch(int i, int j) {
Item item = pq[i];
pq[i] = pq[j];
pq[j] = item;
}

void resize(int newMaxN) {
if (newMaxN < minN) {
if (maxN == minN) return;
else newMaxN = minN;
}
Item *newpq = new Item[newMaxN + 1];
int length = newMaxN > maxN ? maxN : newMaxN;
for (int i = 1; i <= length; ++i) {
newpq[i] = pq[i];
}
delete[] pq;
pq = newpq;
}

void swim(int k) {
while (k > 1 && cmp(k, k / 2)) {
exch(k / 2, k);
k /= 2;
}
}

void sink(int k) {
int j;
while (2 * k <= N) {
j = 2 * k;
j += (j < N && cmp(j + 1, j));
if (cmp(j, k)) {
exch(k, j);
k = j;
} else break;
}
}

public:
BPriorityQueue() {
this->maxN = 5;
this->minN = 5;
pq = new Item[5 + 1];
}

BPriorityQueue(int maxN) {
this->maxN = maxN;
this->minN = maxN;
pq = new Item[maxN + 1];
}

BPriorityQueue(const Item *pq, int size) {
maxN = N = size;
minN = N;
this->pq = new Item[size + 1];
for (int i = 1; i <= N; ++i) {
this->pq[i] = pq[i - 1];
}
for (int k = N / 2; k >= 1; --k) {
sink(k);
}
}

bool isEmpty() {
return N == 0;
}

int size() {
return N;
}

void insert(const Item &item) {
if (N == maxN)
resize(2 * N);
pq[++N] = item;
swim(N);
}

Item pop() {
if (N <= maxN / 4)
resize(maxN / 2);
Item item = pq[1];
exch(1, N);
--N;
sink(1);
return item;
}

const Item &peek() {
return pq[1];
}

virtual ~BPriorityQueue() {
delete[] pq;
}
};

#endif //SBL_BPRIORITYQUEUE_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

constexpr int INF = 0x7fffffff;

template<typename Weight>
class Edge {
private:
int v;
int w;
Weight weight;
public:
Edge(int v = 0, int w = 0, const Weight &weight = Weight()) :
v(v), w(w), weight(weight) {}

const Weight &getWeight() const {
return weight;
}

void setWeight(const Weight &weight) {
Edge::weight = weight;
}

int either() const {
return v;
}

int other(int p) const {
if (p == v) return w;
if (p == w) return v;
throw "Edge: other";
}

bool operator<(const Edge &rhs) const {
return weight < rhs.weight;
}
};

int height[26][26];
int V;

int lazyPrim() {
BPriorityQueue<Edge<int>, bpq::less<Edge<int>>> pq(V * V);
bool *marked = new bool[V]{};
int ans = 0;

auto visit = [&](int v) {
marked[v] = true;
for (int w = 0; w < V; ++w) {
if (w == v || height[v][w] == INF) continue;
pq.insert(Edge(v, w, height[v][w]));
}
};

visit(0);
while (!pq.isEmpty()) {
Edge e = pq.pop();
int v = e.either(), w = e.other(v);
if (marked[v] && marked[w]) continue;
ans += e.getWeight();
if (!marked[v]) visit(v);
if (!marked[w]) visit(w);
}

delete[] marked;
return ans;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> V;
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (i != j)
height[i][j] = height[j][i] = INF;
}
}
for (int v = 0; v < V - 1; ++v) {
char tc;
int count, tmp;
cin >> tc;
cin >> count;
for (int i = 0; i < count; ++i) {
cin >> tc >> tmp;
height[v][tc - 'A'] = height[tc - 'A'][v] = tmp;
}
}

cout << lazyPrim() << endl;
return 0;
}
``````

## q4x3's solution

``````#include <cstdio>

const int MAXN = 30, MAXROAD = 500;
char tmp[4];

template <typename T>
void merge(int lo, int mi, int hi, T* a) {
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}
template <typename T>
void mergeSort(int lo, int hi, T* A) {
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}

struct edge {
int u, v;
int w;
bool operator<(const edge &rhs) {
return w < rhs.w;
}

void link(int u, int v, int w) {
map[u][v] = map[v][u] = ++ tot;
E[tot].u = u, E[tot].v = v, E[tot].w = w;
}

int init() {
for(int i = 1;i <= n;++ i)
fa[i] = i;
}

int find(int x) {
int son = x;
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}

int bind(int x, int y) {
fa[find(x)] = find(y);
}

int main() {
scanf("%d", &n);
for(int i = 1;i < n;++ i) {
scanf("%s", tmp);
for(int j = 1;j <= roadnum;++ j) {
scanf("%s", tmp);
scanf("%d", &val);
link(i, tmp[0] - 'A' + 1, val);
}
}
mergeSort(1, tot + 1, E);
init();
for(int i = 1;i <= tot;++ i) {
if(edgenum == n - 1) break;
if(find(E[i].u) != find(E[i].v)) {
++ edgenum;
ans += E[i].w;
bind(E[i].u, E[i].v);
}
}
printf("%d\n", ans);
}
``````

## victrid's solution

``````#include <cstdio>
#include <iostream>
using namespace std;

struct edge {
int v;
int w;
int weight;

edge& operator=(const edge& rhs) {
v      = rhs.v;
w      = rhs.w;
weight = rhs.weight;
return *this;
}
bool operator<(const edge& rhs) const { return weight < rhs.weight; }
};

edge strage[200];
int treesize;
void swap(edge& a1, edge& a2) {
edge temp = a1;
a1        = a2;
a2        = temp;
return;
};
void insert(edge i) {
strage[++treesize] = i;
int x              = treesize;
while (x != 1) {
if (strage[x] < strage[x >> 1]) {
swap(strage[x], strage[x >> 1]);
x >>= 1;
} else
break;
}
return;
}
edge pop() {
swap(strage[1], strage[treesize]);
treesize--;
int i = 2;
while (i <= treesize) {
if ((i | 1) <= treesize && strage[i | 1] < strage[i])
i |= 1;
if (strage[i] < strage[i >> 1]) {
swap(strage[i], strage[i >> 1]);
i <<= 1;
} else
break;
}
return strage[treesize + 1];
}

int weight[30][30] = {0};
bool visited[30]   = {false};

int total;

void visit(int v) {
if (visited[v])
return;
visited[v] = true;
for (int w = 0; w < total; ++w) {
if (w == v || weight[v][w] == 0)
continue;
insert(edge{v, w, weight[v][w]});
}
}

int main() {
char ch1, ch2;
int a, b, ans = 0;
scanf("%d", &total);
for (int i = total - 1; i; i--) {
scanf(" %c %d", &ch1, &a);
while (a--) {
scanf(" %c %d", &ch2, &b);
weight[ch1 - 'A'][ch2 - 'A'] = weight[ch2 - 'A'][ch1 - 'A'] = b;
}
}
visit(0);
while (treesize) {
edge e = pop();
if (visited[e.v] && visited[e.w])
continue;
ans += e.weight;
visit(e.v);
visit(e.w);
}
printf("%d", ans);
return 0;
}
``````