ABC383E题解

· · 题解

ABC383E 题解

题意

给定一张包含 n 个节点和 m 条无向带权边的图，以及两个序列 A_k,B_k 分别表示图中的某些节点，定义 f(A_i,B_j) 为从 A_i 到 B_j 所有路径各自包含的边权最大值中的最小值，可以任意排列 B 中的元素，使得 \sum_{i=1}^kf(A_i,B_i) 最小化，求出这个最小值。

分析

结论

转化为最小生成树的问题，贪心，在 Kruskal 的过程中额外记录一下每个点集中待匹配的 A,B 元素个数，每次连接两个不连通点集 V_1,V_2 的时候，尽可能多地把 V_1 中的 A 和 V_2 中的 B 匹配，把 V_1 中的 B 和 V_2 中的 A 匹配，代价为：当前边的边权 乘以 匹配数。

证明1

首先，需要明确为什么“当前边的边权”是路径中的“边权最大值”。

根据 Kruskal 算法的原理，我们先对边权进行了排序，那么我们一定是按照边权大小升序排序来枚举边。

假设在枚举过程中，当前枚举到了一条权值为 w，可以连接 u 和 v 两个未连通点的边，那么我们会选择这条边，并把 u,v 所在集合连接起来，所以 u 到 v 路径中一定包含了这条边（因为在最后的最小生成树中，任意两节点之间的路径唯一），并且这条边的边权是当前考虑过的所有边中最大的，显然它也是这条路径上最大的。

在之后对边的枚举中，任何选取都不会对 u,v 路径产生影响了。

证明2

然而这条最小生成树中的路径的情况，只是一条路径的边权最大值，那么它为什么是 u 到 v 所有路径的边权最大值中的“最小值”呢？

采用反证法，记我们在最小生成树的流程中选出来的这条边的边权为 MX1 ，假设存在另一条以 MX2 为边权最大值的路径，使得 MX2<MX1，那么画个图思考一下会发现，我们根本就不会选择 MX1 这条边作为最小生成树的一部分，矛盾，所以假设不成立。

证明3

至于为什么要"尽可能多地匹配"，这一点从贪心地角度想应该是很明了的，由于 B 内部是可以取任意顺序的，又因为我们枚举边的顺序是从小到大，无论如何都要做满 k 次匹配，那肯定是让每一次匹配尽量产生较小的答案，最后的答案一定是最小的。

细节

  2. 开 longlong。

    Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
const int N=2e5+10;
struct Edge
{
    int u,v,w;
    const bool operator <(Edge tmp)const{return w<tmp.w;}
}e[N];
int a[N],b[N];
int fa[N];
int siza[N],sizb[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1,u,v,w;i<=m;++i)
    {
        cin>>u>>v>>w;
        e[i]={u,v,w};
    }
    for(int i=1;i<=k;++i)cin>>a[i],siza[a[i]]++;
    for(int i=1;i<=k;++i)cin>>b[i],sizb[b[i]]++;
    for(int i=1;i<=n;++i)fa[i]=i;
    sort(e+1,e+m+1);
    int ans=0;
    for(int i=1;i<=m;++i)
    {
        int fx=find(e[i].u),fy=find(e[i].v);
        if(fx==fy)continue;
        int w=e[i].w;
        int mn=min(siza[fx],sizb[fy]);
        ans+=w*mn,siza[fx]-=mn,sizb[fy]-=mn;

        mn=min(sizb[fx],siza[fy]);
        ans+=w*mn,sizb[fx]-=mn,siza[fy]-=mn;

        fa[fx]=fy;
        siza[fy]+=siza[fx],sizb[fy]+=sizb[fx];
        siza[fx]=0,sizb[fx]=0;
        //merge
    }
    cout<<ans;
    return 0;
}