题目描述
有 \(N\) 个参赛选手,将进行 \(N-1\) 场比赛,第 \(i,j\) 个选手进行比赛有 \(P_{i,j}\) 的激烈程度。每当选手 \(i\) 打败选手 \(j\) 时,\(P_{i,x}\leftarrow\max(P_{i,x},P_{j.x})\)。
在这些比赛中,编号小的选手总是打败编号大的选手。求最终 \(N-1\) 场比赛的激烈程度之和的最大值并给出方案。
思路
由于打败对手后激烈程度会取最大值,所以可以看作是两个集合 \(S_1,S_2\) 在打比赛,其激烈程度为 \(\min \limits_{x\in S_1,y\in S_2} \{P_{x,y}\}\)。
这实际上就是最小生成树。
但这道题要输出方案,也很好解决。两个集合 \(S_1,S_2\) 打比赛就是 \(\min \limits_{x\in S_1}\{x\},\min \limits_{x\in S_2}\{x\}\) 在打比赛。
空间复杂度 \(O(N^2)\),时间复杂度 \(O(N^2 \log N^2)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1001;
struct Edge {
int u, v, w;
}e[MAXN * MAXN], edge[MAXN];
int n, f[MAXN], sz[MAXN], Min[MAXN], tot;
ll ans;
int getfa(int u) {
return (f[u] == u ? u : f[u] = getfa(f[u]));
}
void Merge(int u, int v) {
u = getfa(u), v = getfa(v);
if(u != v) {
if(sz[u] > sz[v]) {
swap(u, v);
}
f[u] = v, sz[v] += sz[u], Min[v] = min(Min[v], Min[u]);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
sz[i] = 1, f[i] = Min[i] = i;
for(int j = 1, w; j <= n; ++j) {
cin >> w;
e[(i - 1) * n + j] = {i, j, w};
}
}
sort(e + 1, e + n * n + 1, [](const Edge &a, const Edge &b) {
return a.w > b.w;
});
for(int i = 1; i <= n * n; ++i) {
auto [u, v, w] = e[i];
if(getfa(u) != getfa(v)) {
ans += w;
edge[++tot] = {Min[getfa(u)], Min[getfa(v)], w};
Merge(u, v);
}
}
cout << ans << "\n";
for(int i = 1; i < n; ++i) {
cout << edge[i].u << " " << edge[i].v << "\n";
}
return 0;
}
标签:sz,比赛,Min,int,GYM,MAXN,getfa,104114
From: https://www.cnblogs.com/yaosicheng124/p/18409040