自动搬运

查看原文

来自洛谷，原作者为

	SAMSHAWCRAFT 疠疫俾惊，荒时殆情。

搬运于2025-08-24 22:14:31，当前版本为作者最后更新于2024-08-04 10:33:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解旨在补充其他题解做法的推理过程。

注意本题中特别提及了点数是奇数，即 $n \bmod 2 = 1$，而本图是一个 $n$-完全图，即 $(n-1)$-正则图，这意味着每个顶点的度数都是 $n-1$，这是一个偶数，不妨设 $n-1=2i$，则在这个图的环分割当中，每个顶点都被且仅被 $i$ 个环通过，且每个环上通过这个顶点的边有且只有 $2$ 条。

接下来思考如何统计答案，通过前面分析，一个顶点的 $2i$ 条边中一定有且只有 $i$ 条被统计进了答案当中，至于这 $i$ 条边分别属于哪个环其实并不重要。可以构造性地证明：假设 $e_x$ 是被统计在答案当中的 $i$ 条边之一，$e_y$ 是未被统计在答案当中的 $i$ 条边之一，只要保证 $f(e_x,e_y)$ 就是 $e_x$ 的边权即可，这样我们就可以把 $e_x$ 和 $e_y$ 放进一个环当中而不需担心这两条边具体在哪一个环，因此这个构造转化成下面的问题：给一个长度为 $2i$ 的序列 $\{w\}$，要把这个序列分成 $i$ 对不相交的元组 $(w_{x_j},w_{y_j})$ 使得 $w_{x_j} \ge w_{y_j}$ 对任意的 $j \in [1,i]$ 成立，求最小化的

这是一个贪心问题，给序列从小到大排序，然后使 $x_j=2j,y_j=2j-1$ 就可以取得最小值。这样的话本题就完成了，代码如下。

#include <iostream>
#include <algorithm>
#include <vector>
const int sz=1e3+9;
int n,m;
long long ans;
std::vector<int> edges[sz];
int main(){
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cout.sync_with_stdio(false);
  std::cin>>n;
  m=(n*(n-1))>>1;
  for(int cx=0,u,v,w;cx!=m;++cx){
    std::cin>>u>>v>>w;
    edges[u].push_back(w);
    edges[v].push_back(w);
  }
  for(int cx=1;cx<=n;++cx)
    std::sort(edges[cx].begin(),edges[cx].end());
  for(int cx=1;cx<=n;++cx){
    for(int cy=1;cy!=n;cy+=2)
      ans+=edges[cx][cy];
  }
  std::cout<<ans<<std::endl;
  return 0;
}