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<XM1\) ，那么画个图思考一下会发现，我们根本就不会选择 \(MX1\) 这条边作为最小生成树的一部分，矛盾，所以假设不成立。
证明3
至于为什么要"尽可能多地匹配"，这一点从贪心地角度想应该是很明了的，由于 \(B\) 内部是可以取任意顺序的，又因为我们枚举边的顺序是从小到大，无论如何都要做满 \(k\) 次匹配，那肯定是让每一次匹配尽量产生较小的答案，最后的答案一定是最小的。
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;
}