まず、\(f(x,y)\) の性質について考えます。

\(f(x,y)\) は 重みが \(w\) 以下である辺だけの部分グラフにおいて頂点 \(x\) と頂点 \(y\) が連結になるような \(w\) としてありえる最小値と等しいです。このことから、相異なる \(3\) 頂点 \(x,y,z\) において \(f(x,y) \leq f(x,z)\) ならば\(f(x,z)=f(y,z)\) が言えます。

これがどういう意味かというと、重み \(w\) 以下の辺で連結である頂点 \(x,y\) について、そのグラフにおいて連結でない頂点 \(z\) とは \(f(x,z)=f(y,z)\) であるということです。

また、この問題は \(B\) を並べ替える問題から \(A\) の要素と \(B\) の要素をマッチングさせるというような言い換えができます。

よって、以下のような貪欲法が考えられます。以降、辺が重みの昇順でソートされていて、\(w_1 \leq w_2 \ldots \leq w_M\) であるとします。

• はじめに \(N\) 頂点の辺がないグラフがある。また、各頂点についてその頂点が \(A\) に含まれるかと、\(B\) に含まれるかをそれぞれ管理します。
• \(i=1,2,\ldots,M\) の順に以下を行う。
  • 頂点 \(u_i,v_i\) が連結でない場合、グラフに辺 \(\{u_i,v_i\}\) を追加する。 連結である場合は次の辺に行く。
  • 辺の追加によって異なる \(2\) つの連結成分が連結になったとき、片方の連結成分に含まれる \(A\) の頂点ともう片方に含まれる \(B\) の頂点をペアがあるだけマッチさせる。
  • マッチした数だけ \(w_i\) を答えに加算する
  • その連結成分に残っている \(A\) もしくは \(B\) に含まれる頂点を更新する。

この貪欲法によってできた \(A\) の要素と \(B\) の要素のマッチングが実は最適解です。

この問題では実際の \(A\) の要素と \(B\) の要素のマッチングを求める必要はないため、頂点自体を管理せずに \(A\) の要素である頂点の個数、\(B\) の要素である頂点の個数(被りを含む) を管理するだけでよいです。

連結成分の管理は Union Find などで適切に行うことができ、また辺を重みで一度ソートするため、計算量は \(\mathrm{O}(M\log M+(N+M) \alpha (N))\) となります(\( \alpha(N)\) は逆アッカーマン関数)。詳細は実装例をご参照ください。

実装例(C++):

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using ll = long long;
static constexpr ll inf = 2e18;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<tuple<int, int, int>> edges(m);
    vector<int> a(k), b(k);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        edges[i] = {w, u, v};
    }
    for (int i = 0; i < k; ++i) cin >> a[i];
    for (int i = 0; i < k; ++i) cin >> b[i];

    vector<int> cnt_a(n), cnt_b(n); // 各連結成分の A の個数, Bの個数
    for (int i = 0; i < k; ++i) {
        cnt_a[a[i] - 1]++;
        cnt_b[b[i] - 1]++;
    }
    sort(edges.begin(), edges.end());
    long long ans = 0;
    atcoder::dsu d(n);
    for (int i = 0; i < m; ++i) {
        auto [c, u, v] = edges[i];
        if (d.same(u, v)) continue; //すでに連結ならば無視する
        int ru = d.leader(u), rv = d.leader(v);
        d.merge(u, v);
        int new_root = d.leader(u);
        cnt_a[new_root] = cnt_a[ru] + cnt_a[rv];
        cnt_b[new_root] = cnt_b[ru] + cnt_b[rv];
        ans += 1LL * c * min(cnt_a[new_root], cnt_b[new_root]); //あるだけペアを作る
        const int e = min(cnt_a[new_root], cnt_b[new_root]);
        cnt_a[new_root] -= e;
        cnt_b[new_root] -= e;
    }

    cout << ans << endl;
}