「LOJ10067」构造完全图

题目链接:LOJ10067

Description

原题描述很详细。

Data Range

$1\leq n\leq 10^5,1\leq L_i\leq 10^5$

Solution

我咋觉得这个题目很难呢?qwq,发现网上的题解没有一篇写的完整的。
首先需要了解几个前置知识。

引理1

对于一条存在于最小生成树上的边$E(u,v,w)$,满足$E_w$为$u$和$v$相连的权值严格最小边。

这个引理的证明和Prim算法的证明相同。
回到原题,我们考虑每一条边$E(u,v,w)$,那么这条边将整颗树划分为两个联通块,我们记录两个联通块的大小为$size1$和$size2$。
那么显然的结论是我们两边的联通块的所有点关于这条边$E$,它的贡献为$(size1*size2-1)*(w+1)$。
那么我们可以得到一个比较显然的贪心,每条边从大到小贪心,把这个边的贡献考虑掉,然后合并联通块,这样保证了最后的联通块合并(也就是最大的两块)的代价最小。
但是这样是错误的。

对于一个点对$(u,v)$的答案贡献为$max(u->v)+1$,所以我们需要从小到大排序后合并,这要保证了每个点对的答案都是最大值+1。

所以我觉得这道题目的正解不是贪心,而是用贪心保证了正确性,最优策略是由引理1保证的。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct _edge{
  int u,v;
  ll w;
  bool operator <(const _edge&rhs)const{
    return w<rhs.w;
  }
}edge[N];
int n;
int fa[N],siz[N];
ll ans=0ll;
int getFa(int u){
  return u==fa[u]?fa[u]:fa[u]=getFa(fa[u]);
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<n;i++){
    scanf("%d%d%lld",&edge[i].u,&edge[i].v,&edge[i].w);
    ans+=edge[i].w;
  }
  sort(edge+1,edge+n);
  for(int i=1;i<=n;i++)
    fa[i]=i,siz[i]=1;
  for(int i=1;i<n;i++){
    int p1=getFa(edge[i].u),p2=getFa(edge[i].v);
    ans+=1ll*(edge[i].w+1)*(siz[p1]*siz[p2]-1);
    fa[p1]=p2;
    siz[p2]+=siz[p1];
  }
  printf("%lld\n",ans);
  return 0;
}
最后修改:2019 年 10 月 10 日 07 : 49 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论