2022-0504-MST¶
| USACO 2015 Feb S. Superbull | 提高 | https://www.luogu.com.cn/problem/P4826 |
|---|---|---|
| Slim Span, ACM/ICPC Japan 2007 | 提高+ | https://www.luogu.com.cn/problem/UVA1395 |
| POJ2349 Arctic Network | 提高 | http://bailian.openjudge.cn/practice/2349/ |
| [JSOI2010]部落划分 | 提高 | https://www.luogu.com.cn/problem/P4047 |
| USACO 2016 Feb G. Fenced In | 提高 | https://www.luogu.com.cn/problem/P6171 |
| USACO 2019 Open G. I Would Walk 500 Miles | 提高 | https://www.luogu.com.cn/problem/P5425 |
| Buy or Build, SWERC 2005, UVa1151 | 提高+ | https://www.luogu.com.cn/problem/UVA1151 |
Superbull¶
/**
* @file luogu/4826/main.cpp
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @brief 一共有 n 头牛参加淘汰赛，每次比赛的分数为两头牛 id 的按位异或，
* 每次比赛后淘汰一头牛，问最大的分数总和
*
* 1. 有 n 头牛
* 2. 有 n-1 场比赛
* 3. 对每一头牛，除了最后的赢家，有且仅有一头战胜自己的牛
* 4. 最后的赢家没有战胜它的牛
*
* 很显然是树的性质，计算每两头牛之间比赛的分数，求最大生成树。
*
* @version 0.1
* @date 2022-05-01
*
* @copyright Copyright (c) 2022
*
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010;
ll id[N];
int par[N * N];
struct edge {
int u, v;
ll cost;
bool operator<(const edge &b) const { return cost > b.cost; } // 反向排序
};
vector<edge> match;
int n;
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> id[i];
// 枚举，让牛两两比赛
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
match.push_back({i, j, id[i] ^ id[j]});
}
}
// Kruskal 最小生成树
ll ans = 0;
int cnt = 0;
for (int i = 0; i < n * n; ++i) par[i] = i;
sort(match.begin(), match.end());
for (int i = 0; i < match.size(); ++i) {
auto [u, v, cost] = match[i];
u = find(u), v = find(v);
if (u == v) continue;
par[u] = v;
ans += cost;
cnt++;
if (cnt == n - 1) break;
}
cout << ans << endl;
}Slim Span¶
/**
* @file uva/1395/main.cpp
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @brief
* 给定一张图，求一棵生成树，使其最大边权与最小边权差最小，输出它们的差值
* 如果图存在生成树，输出生成树的差值最小的；否则，输出-1。
*
* 对于每一个边都从它开始Kruskal一遍并更新答案
* @version 0.1
* @date 2022-05-01
*
* @copyright Copyright (c) 2022
*
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct edge {
int u, v, w;
bool operator<(const edge &b) const { return w < b.w; }
} e[N];
typedef long long ll;
int n, m;
int par[N];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
int maxedge;
bool kruskal(int start_from) {
for (int i = 1; i <= n; ++i) par[i] = i;
int cnt = 0;
maxedge = -1;
for (int i = start_from; i <= m; ++i) {
auto [u, v, w] = e[i];
u = find(u), v = find(v);
if (u == v) continue;
par[u] = v;
if (++cnt == n - 1) {
// 保存最大边权
maxedge = w;
return true;
}
}
return false;
}
int main() {
while (scanf("%d%d", &n, &m) != EOF && n) {
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
int ans = 0x3f3f3f3f;
sort(e + 1, e + m + 1);
for (int i = 1; i <= m; ++i) {
// 从第 i 条边开始计算生成树
if (kruskal(i)) {
ans = min(ans, maxedge - e[i].w);
}
}
cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
}
}Arctic Network¶
/**
* @file poj/2349/main.cpp
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @brief 每一个outpost都会配有电波接收器，一些outpost会配有卫星接收器
* 电波接收器有一定工作范围，都为D；卫星的工作范围是无限。
* 求最小的D使得任意两点可以直接或间接通信。
*
* 通过连接 n - s 条边使得图有 s 个连通分量
* 输出MST第 n - s 条边的权重即可
*
* @see <http://bailian.openjudge.cn/practice/2349/>
* @see <http://bailian.openjudge.cn/practice/solution/34259329/>
* @version 1.0
* @date 2022-05-02
*
* @copyright Copyright (c) 2022
*
**/
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int x[N], y[N];
int s, n;
struct edge {
int u, v;
double d;
bool operator<(const edge &b) const { return d < b.d; }
};
vector<edge> E;
inline double dist(int u, int v) {
double dx = x[u] - x[v], dy = y[u] - y[v];
return sqrt(dx * dx + dy * dy);
}
int par[N];
inline int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> s >> n;
for (int i = 0; i <= n; ++i) par[i] = i;
E.clear(); // 记得清全局变量
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
// 计算点对距离并排序
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) E.push_back({i, j, dist(i, j)});
sort(E.begin(), E.end());
int cnt = 0;
for (auto [u, v, cost] : E) {
u = find(u), v = find(v);
if (u == v) continue;
par[u] = v;
if (++cnt == n - s) {
printf("%.2lf\n", cost);
break;
}
}
}
}部落划分¶
并查集，不断合并最近的，直到剩\(k\)个集合。
/**
* P4047 [JSOI2010]部落划分
**/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+8;
int n, k;
int x[maxn], y[maxn];
struct p {
int u, v, dist;
p() = default;
p(int a, int b):u(a), v(b){
int dx = abs(x[a]-x[b]), dy=abs(y[a]-y[b]);
dist = dx*dx+dy*dy;
}
bool operator < (const p &b) const {return dist<b.dist;}
}dist[maxn*maxn];
int tot, merged;
int par[maxn];
void init() {for(int i=1; i<n; ++i) par[i]=i;}
int find(int x) {return x==par[x]?x:par[x]=find(par[x]);};
void unite(int u, int v) {par[find(u)]=find(v);}
bool same(int u, int v) {return find(u)==find(v);}
int main() {
scanf("%d%d\n", &n, &k);
for(int i=0; i<n; ++i) {
scanf("%d%d", x+i, y+i);
}
init();
for(int i=0; i<n; ++i) {
for(int j=i+1; j<n; ++j) {
dist[tot++] = p(i, j);
}
}
sort(dist, dist+tot);
int nclans = n;
int cnt;
for(cnt=0; cnt<tot; ++cnt) {
// Make it C++11 Compatible
// auto [u, v, d] = dist[cnt];
auto u = dist[cnt].u;
auto v = dist[cnt].v;
auto d = dist[cnt].dist;
if(!same(u, v)) {
unite(u, v);
nclans--;
if(nclans==k) break;
}
}
for(;cnt<tot; ++cnt) {
// auto [u, v, d] = dist[cnt];
auto u = dist[cnt].u;
auto v = dist[cnt].v;
auto d = dist[cnt].dist;
if(same(u, v)) continue;
else {
printf("%.2f\n", sqrt(d));
break;
}
}
}Fenced In¶
/**
* @file luogu/6171/main.cpp
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @brief
* @version 0.1
* @date 2022-05-01
* @url https://www.luogu.com.cn/record/74966952
*
* @copyright Copyright (c) 2022
*
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2004;
int pa[N * N];
int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); }
bool merge(int x, int y) {
x = find(x), y = find(y), pa[x] = y;
return x != y;
}
int a, b, m, n;
int enc(int r, int c) { return r * m + c; }
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> a >> b >> n >> m;
vector<int> w(n + 1), h(m + 1);
for (int i = 0; i < n; ++i) cin >> w[i];
sort(w.begin(), w.end());
for (int i = 0; i < n; ++i) w[i] = w[i + 1] - w[i];
w[n] = b - w[n];
for (int i = 0; i < m; ++i) cin >> h[i];
sort(h.begin(), h.end());
for (int i = 0; i < m; ++i) h[i] = h[i + 1] - h[i];
h[m] = a - h[m];
sort(w.begin(), w.end()), sort(h.begin(), h.end()), n++, m++;
for (int i = 0; i < n * m; ++i) pa[i] = i;
long long ans = 0;
for (int vi = 0, hi = 0; vi < n || hi < m;) {
if (hi == m || vi < n && w[vi] < h[hi]) {
for (int i = 0; i < m - 1; ++i) {
if (merge(enc(vi, i), enc(vi, i + 1))) ans += w[vi];
}
vi++;
} else {
for (int i = 0; i < n - 1; ++i) {
if (merge(enc(i, hi), enc(i + 1, hi))) ans += h[hi];
}
hi++;
}
}
cout << ans << endl;
}
Would Walk 500 Miles¶
玄学：开-O2会错
#include <bits/stdc++.h>
using namespace std;
const int NN = 7500;
int N, K, Vis[NN];
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)
using LL = long long;
const LL MOD = 2019201997, A = 2019201913LL, B = 2019201949LL;
LL D[NN];
LL prim() { // Prim/Jarnik MST algorithm
_all(i, 1, N) D[i] = MOD;
_all(iter, 1, N) {
int mi = 0;
_all(i, 1, N) if (!Vis[i] && (mi == 0 || D[i] < D[mi])) mi = i;
Vis[mi] = 1;
_all(i, 1, N) if (!Vis[i]) D[i] =
min(D[i], (A * min(mi, i) % MOD + B * max(mi, i)) % MOD) % MOD;
}
sort(D + 1, D + N + 1);
return D[N + 1 - K];
}
int main(void) {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> K;
cout << prim() << "\n";
return 0;
}Buy or Build¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 10, Q = 8;
int n, x[N], y[N], cost[N];
vector<int> subn[Q];
int pa[N];
int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; }
struct Edge {
int u, v, d;
Edge(int u, int v, int d) : u(u), v(v), d(d) {}
bool operator<(const Edge& rhs) const { return d < rhs.d; }
};
/**
* @brief 求MST
*
* initialize `pa` and sort `e` before calling this method.
* `cnt` is the current number of components
*
* @param cnt 当前连通分量的个数
* @param e 可用的边集
* @param used 返回已使用的边集
* @return 新加入MST的边的权重之和
*/
int MST(int cnt, const vector<Edge>& e, vector<Edge>& used) {
if (cnt == 1) return 0;
int m = e.size();
int ans = 0;
used.clear();
for (int i = 0; i < m; ++i) {
int u = findset(e[i].u), v = findset(e[i].v);
int d = e[i].d;
if (u != v) {
pa[u] = v;
ans += d;
used.push_back(e[i]);
if (--cnt == 1) break;
}
}
return ans;
}
int main() {
int T, q;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &q);
for (int i = 0; i < q; ++i) {
int cnt;
scanf("%d%d", &cnt, &cost[i]);
subn[i].clear(); // 清掉上一次的，别忘了
while (cnt--) {
int u;
scanf("%d", &u);
subn[i].push_back(u - 1);
}
}
for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);
vector<Edge> e, // 边集
need; // 如果某条边不在MST中，这条边也不会出现在买了子网后的生成树中。
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
int c = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
e.push_back(Edge(i, j, c));
}
for (int i = 0; i < n; ++i) pa[i] = i;
sort(e.begin(), e.end());
int ans = MST(n, e, need); // 1. 一个都不买
// 2. 至少买一个
for (int mask = 1; mask < (1 << q); ++mask) {
// 买下子网，将子网内部连到一起
for (int i = 0; i < n; ++i) pa[i] = i;
int cnt = n, // 最开始，有n个连通分量
c = 0; // 本次花费
for (int i = 0; i < q; ++i)
if (mask & (1 << i)) {
c += cost[i]; // 买子网，加到同一个连通分量中
for (int j = 1; j < subn[i].size(); ++j) {
int u = findset(subn[i][j]), v = findset(subn[i][0]);
if (u != v) {
pa[u] = v;
cnt--;
}
}
}
vector<Edge> dummy;
// 子网消耗 + 继续连通
ans = min(ans, c + MST(cnt, need, dummy));
}
printf("%d\n", ans);
if (T) printf("\n");
}
return 0;
}