题解：SP8980 KOICOST - Cost

· · 题解

题解：SP8980 KOICOST - Cost

不错的题目，代码与题目相互呼应，声光交融，指尖灵动，即使是我，也感到心潮澎湃。

这道题意思还是挺好懂的，我们直接开始思考。

直接求 \sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{Cost}(x,y) 是不可行的，所以我们需要换一个视角。我们可以这样想，我们是否可以求每一条边对答案的贡献呢？显而易得，可以。

怎么求？经过大量的数据枚举（我是真的这么做了），我们可以发现，每条边 e 对答案的贡献实际上只比它大的边所形成的连通结构有关。更详细的说，定义 f(u,v) 为 u 到 v 所有路径上最大边权的最小值，那么 \operatorname{Cost}(u,v) 就等于所有边权小于等于 f(u,v) 的边的权值和（因为边权从小到大删边，u 和 v 在删完边权小于等于 f(u,v) 的边后刚好断开）。

因此，一条权值为 w 的边 e 会被计入 \operatorname{Cost}(u,v) 中当且仅当 f(u,v) \ge w，也就是 u 和 v 在“仅保留权值大于等于 w 的边”的子图中是连通的。

所以，怎么转换成代码？其实代码的写法和思路有一些差别，在我们的思考中，我们是枚举边看它对答案的贡献，然而在代码实现中，则是枚举满足 f(u,v)=w 的点对 (u,v)，它们恰好分别位于即将合并的两个不同集合中，并在合并集合时一次性计算这些新产生的点对对答案的贡献。

形象地说，如果一条权值为 w 的边 e 连接了两个端点暂没有连接的集合，并且这两个集合内部已经被所有边权大于 w 的边连通，那么连接后，新产生的点对 (u,v)（即分别来自于两个集合）正好满足 f(u,v) = w，因此，所有边权小于等于 w 的边都会对答案贡献自己的边权值，每一个新点对都是如此。容易得到，若两个集合的大小分别为 siz_u 和 siz_v，所有边权小于等于 w 的边的边权和为 sum，那么这次对答案的贡献为 siz_u \times siz_v \times sum。

通过集合，我们很容易就能想出，我们可以通过并查集来遍历，按边权从大到小处理。每次遇到一条边权为 w、连接了 u 和 v 两个点的边，先找到 u 和 v 两个点所在的集合的根节点 fx 和 fy，如果它们不在同一集合，那么合并后新产生的点对数为 siz_{fx} \times siz_{fy}，将其乘上所有边权小于等于 w 的边的边权和 sum，即贡献为 siz_{fx} \times siz_{fy} \times sum，然后合并两个集合，将 sum 减去 w（因为当前边已经从剩余边集中移除，后续只会处理更小的边）。如果 u 和 v 在同一集合，则不会产生新点对，跳过，但 sum 仍需减去 w，因为之后的更小边依旧不再包含当前边。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+111;
const int mod=1e9;
vector<pair<int,pair<int,int>>>edge;
int n,m;
int fa[N],siz[N];
int find(int u){
    if(fa[u]!=u){
        fa[u]=find(fa[u]);
    }
    return fa[u];
}
int make(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx==fy){
        return 0;
    }
    fa[fx]=fy;
    int k=siz[fx]*siz[fy]%mod;
    (siz[fy]+=siz[fx])%=mod;
    return k;
}
void _init(){
    for(int i=1;i<=N-11;i++){
        fa[i]=i;
        siz[i]=1;
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    _init();
    int sum=0,ans=0;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        edge.push_back({z,{x,y}});
        sum+=z;
    } 
    sort(edge.rbegin(),edge.rend());
    for(int i=0;i<edge.size();i++){
        int z=edge[i].first,x=edge[i].second.first,y=edge[i].second.second;
        (ans+=make(x,y)*sum%mod)%=mod;
        sum-=z;
    }
    printf("%lld",ans);
    return 0;
}