Kruskal求最小生成树
#include <iostream>
#include <algorithm>
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
const int N = 2E3 + 1E2;
int edge_cnt;
struct Edge {
int u, v, w;
bool operator<(const Edge& o) const {
return w < o.w;
}
} edges[N * N];
int n;
struct UnionFind {
public:
UnionFind() { f(i, 0, N) p_[i] = i; }
int find(int x) {
if (p_[x] ^ x) p_[x] = find(p_[x]);
return p_[x];
}
bool unite(int p, int q) {
int root_p = find(p), root_q = find(q);
if (root_p == root_q) return false;
p_[root_p] = root_q;
return true;
}
private:
int p_[N];
};
inline int kruskal(void) {
sort(edges, edges + edge_cnt);
UnionFind uf;
int tot_cost = 0, cnt = 0;
f(e, 0, edge_cnt) {
int u = edges[e].u, v = edges[e].v, w = edges[e].w;
if (not uf.unite(u, v)) continue;
tot_cost += w;
if (++cnt == n - 1) return tot_cost;
}
return 0;
}
int main(int argc, char const *argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >> n, n) {
string nodes[n];
f(i, 0, n) cin >> nodes[i];
edge_cnt = 0;
f(i, 0, n) f(j, i + 1, n) {
int w = 0;
f(k, 0, 7) w += nodes[i][k] != nodes[j][k];
edges[edge_cnt++] = {int(i), int(j), w};
}
printf("The highest possible quality is 1/%d.\n", kruskal());
}
return ~~(0 ^ 0);
}