11566: 【原1566】最小生成树问题
题目
题目描述
author: 孙梦璇 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1566
Description
某个小岛的族长遇到了一个问题。多年以前一大笔国外援助资金花在了建筑村庄间的大批道路上，但是多年以来森林侵蚀了很多道路，因此维护如此巨大的道路网络过于昂贵。族长必须停止维护一些道路。当然，通过剩余还在维护的道路，各个村庄之间互相连通，尽管路程不像以前那样短了。族长必须决定在连通所有村庄的条件下，每月花费的最少维护费用。村庄以大写英文字母编号（从A开始）。你的任务是写一个程序来解决上面的问题。
Input Format
每个数据集以一个数字n开头，代表着村庄数目，1<n<27，村庄以字母表中前n个大写字母表示。接下来n—1行每行以一个大写英文字母开头，各行开头的大写英文字母以字母表的顺序排列，不包含最后一个村庄。每行中，代表村庄号的大写字母之后是一个数字k，代表着连接着这个村庄和其他村庄的道路数目（每行中其他村庄的编号在字母表中的顺序都在开头的村庄编号之后），如果k大于零，k之后就是k个道路的信息。每条道路的信息为道路另一端的村庄编号和这条道路每月的维护费用，维护费用是小于100的正整数。行中的数据以空白符隔开。道路网络始终能保证村庄间互相连通。道路网络中的道路数不会超过75个。每个村庄拥有的连接其他村庄的道路数不超过15个。
Output Format
输出 每行有一个整数，对应着一个数据集：在连通所有村庄的条件下，每月花费的最少的维护费用。提示：对所有可能的道路的暴力搜索不能在一分钟的时限内完成。
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;
int n, roadnum, val, tot, map[MAXROAD][MAXROAD], edgenum, fa[MAXN], ans;
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;
}
} E[MAXROAD];
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);
scanf("%d", &roadnum);
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;
}