P5805 [SEERC2019] Graph and Cycles 题解

· · 题解

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

注意本题中特别提及了点数是奇数，即 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] 成立，求最小化的

\sum_{j=1}^i w_{x_j}

这是一个贪心问题，给序列从小到大排序，然后使 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;
}