题目
肯千网络公司最新推出了完全由偶像一对一对战构成的网络选秀节目。在该节目中，节目组邀请了 n 位偶像，每天举办一场比赛，从仍然存活的偶像中选出两位进行一对一的PK，胜者将得到奖金，败者则将离开这个游戏，在之后不能再上台进行比赛。就这样进行 n−1 场比赛，直到只剩下最后的偶像作为最终的冠军。 由于偶像之间的各种绯闻和恩恩怨怨，公司经过调查发现，如果第 i 位偶像和第 j 位偶像进行比赛，会给节目增加 f(i,j) 的热度。 作为这个节目的运营，你可以任意挑选每天进行比赛的两名选手，甚至可以暗中操控比赛的胜负！你当然希望使得最终节目的总热度最大。那么，节目的总热度最多是多少呢？
题目链接
https://citel.bjtu.edu.cn/acm/problem/1929
输入数据
第一行为一个整数 n (1≤n≤1000)，表示偶像的个数。
接下来 n−1 行，第 i 行有 n−i 个数，第 j 个数表示 f(i,i+j)，即第 i 位偶像和第 i+j 位偶像进行比赛增加的热度值 (1≤f(i,i+j)≤10^8)。
输出数据
一个整数，为通过一路黑箱选出冠军的过程中节目的最大总热度。
样例输入
5
7 3 3 3
9 3 3
8 12
3
样例输出
36
样例说明
对战安排及胜利情况如下：
3−5，热度 12，3获胜，
1−2，热度 7，2获胜，
3−4，热度 8，3获胜，
2−3，热度 9，冠军无论是谁都可以。
最后总热度 12+7+8+9=36。
可以证明，不存在更优的安排方案。
问题分析
这个问题可以转化为：在 n 个点的图中，每两个点之间都有一条无向边，即总边数为k = n * (n - 1)，构造出一个树（边数为n-1），求树的边长之和的最大值。
数据结构中有一个经典的问题是最小生成树（其实离散数学里也学过），只要将最小生成树更改为最大生成树就可以解决本题了。
我这里使用的是Kruskal算法。
记录所有边的信息，对边按照长度从大到小排序。然后枚举每一条边，如果这条边加入子图会产生环则抛弃这条边，反之则将其加入子图。
如何去维护子图呢？或者说如何判断有没有生成环？
使用并查集就ok了。对于一条边，判断它两个顶点的root是否相同，如果相同则说明会产生环。如果不相同，就把它的两个顶点merge一下，相当于添加到子图。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int f[MAXN][MAXN];
struct edge
{
int from, to, len;
edge(int from1, int to1, int len1) : from(from1), to(to1), len(len1)
{
}
edge()
{
}
bool operator<(const edge &s2)
{
return len > s2.len;
}
} e[1000005];
int i, n, ufs[MAXN];
void Init()
{
for (i = 0; i < MAXN; i++)
{
ufs[i] = i;
}
}
int getroot(int n)
{
if (ufs[n] != n)
ufs[n] = getroot(ufs[n]);
return ufs[n];
}
void merge(int a, int b)
{
int x = getroot(a), y = getroot(b);
if (x != y)
ufs[x] = y;
}
int main()
{
Init();
int j, k, len, sum = 0, a, b, minnum = 0, NumOfEdge = 0;
long long ans = 0;
scanf("%d", &n); //n个点k条边
k = n * (n - 1);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n - i; j++)
{
scanf("%d", &f[i][i + j]);
e[NumOfEdge++] = edge(i, i + j, f[i][i + j]);
}
}
sort(e, e + NumOfEdge);
for (i = 0; i < NumOfEdge; i++)
{
a = e[i].from, b = e[i].to;
if (getroot(a) != getroot(b))
{
merge(a, b);
ans += e[i].len;
}
}
printf("%lld\n", ans);
return 0;
}