1. 题目

传送门=￣ω￣=

2. 题解

好神的题啊

首先点数 $100000$太多了，我们可以想到 $m$条边中有的边无论你那 $k$条边怎么定价都是会出现的。

找出这些边的方法就是先把那 $k$条边加入一个空的图中，然后从小到大依次加入 $m$条边，如果加入某条边的时候它的两个端点没有联通，则说明即使 $k$条边全选也无法联通这两个端点，因此当前这条边是一定会出现的。

于是我们把那些被这些边联通的点缩成一个点，因为在它们之间移动是没有代价的。

那么剩下只有 $k + 1$个点了（后面为了书写方便我们暂时当它只有 $k$个点）

然后有很多边是没用的，排除它们以后就只剩下 $k ^ 2$条边了。

接着我们枚举 $k$条可定价边的选择状态（选或者不选）：

• 如果选择的边构成了环，那么这种选择方式不合法，直接 continue
• 对于合法的选择方案，从小到大依次加入 $k ^ 2$条边
  • 如果当前加入的边的两个端点还未被联通，则联通这两个端点
  • 如果当前加入的边的两个端点已经被联通了，则树上这两点之间的路径上的可定价边的最大价格不得超过当前这条边的价格

于是这题就做完了，维护最小值的操作我是用的暴力，复杂度 $O(m log m + 2 ^ k k ^ 3)$

发现可能会超时，开个 O2 就行啦

#include <bits/stdc++.h>

#define NS (100005)
#define MS (300005)
#define KS (25)
#define FIR first
#define SEC second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct Edge {int u, v, d;} E[MS], Q[MS];

int n, m, k, Su[KS], Sv[KS], Peo[NS], Blk[NS], bc, qc;

LL Man[KS];

int fa[NS];

int findf(int a) {return fa[a] == a ? a : fa[a] = findf(fa[a]);}

bool Key_Edge[MS];

bool cmp(Edge a, Edge b) {return a.d < b.d;}

void Mini()
{
    for (int i = 1; i <= n; i += 1) fa[i] = i;
    int tot = 0;
    for (int i = 0; i < k; i += 1)
        if (findf(Su[i]) != findf(Sv[i]))
            fa[findf(Su[i])] = findf(Sv[i]), tot++;
    sort(E + 1, E + 1 + m, cmp);
    for (int i = 1; tot < n - 1; i += 1)
        if (findf(E[i].u) != findf(E[i].v))
        {
            fa[findf(E[i].u)] = findf(E[i].v);
            Key_Edge[i] = 1, tot++;
        }
    for (int i = 1; i <= n; i += 1) fa[i] = i;
    for (int i = 1; i <= m; i += 1)
        if (Key_Edge[i]) fa[findf(E[i].u)] = findf(E[i].v);
    Blk[findf(1)] = bc = 1;
    for (int i = 2; i <= n; i += 1)
        if (fa[i] == i && !Blk[i]) Blk[i] = ++bc;
    for (int i = 1; i <= n; i += 1)
        Blk[i] = Blk[findf(i)], Man[Blk[i]] += Peo[i];
    for (int i = 1; i <= m; i += 1)
        if (findf(E[i].u) != findf(E[i].v))
        {
            fa[findf(E[i].u)] = findf(E[i].v), Q[++qc] = E[i];
        }
}

vector<PII> g[KS];

int pre[KS], dis[KS], dep[KS];

bool book[KS];

LL ans, res;

void Init(int a)
{
    for (int i = 0, tmp; i < g[a].size(); i += 1)
        if (tmp = g[a][i].FIR, tmp != pre[a])
        {
            pre[tmp] = a, dis[tmp] = g[a][i].SEC;
            if (dis[tmp] > 1e9) book[tmp] = 1;
            dep[tmp] = dep[a] + 1, Init(tmp);
        }
}

void Cal(int a, int tot)
{
    if (book[a]) tot += dis[a];
    res += Man[a] * tot;
    for (int i = 0, tmp; i < g[a].size(); i += 1)
        if (tmp = g[a][i].FIR, tmp != pre[a])
            Cal(tmp, tot);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(k);
    for (int i = 1; i <= m; i += 1) IN(E[i].u), IN(E[i].v), IN(E[i].d);
    for (int i = 0; i < k; i += 1) IN(Su[i]), IN(Sv[i]);
    for (int i = 1; i <= n; i += 1) IN(Peo[i]);
    Mini();
    for (int bs = 1; bs < (1 << k); bs += 1)
    {
        for (int i = 1; i <= bc; i += 1) book[i] = 0, g[i].clear(), fa[i] = i;
        for (int i = 0; i < k; i += 1)
            if ((bs >> i) & 1)
            {
                if (findf(Blk[Su[i]]) == findf(Blk[Sv[i]])) goto end;
                fa[findf(Blk[Su[i]])] = findf(Blk[Sv[i]]);
                g[Blk[Su[i]]].push_back(PII(Blk[Sv[i]], INT_MAX));
                g[Blk[Sv[i]]].push_back(PII(Blk[Su[i]], INT_MAX));
            }
        for (int i = 1; i <= qc; i += 1)
            if (findf(Blk[Q[i].u]) != findf(Blk[Q[i].v]))
            {
                fa[findf(Blk[Q[i].u])] = findf(Blk[Q[i].v]);
                g[Blk[Q[i].u]].push_back(PII(Blk[Q[i].v], Q[i].d));
                g[Blk[Q[i].v]].push_back(PII(Blk[Q[i].u], Q[i].d));
            }
        Init(1);
        for (int i = 1; i <= qc; i += 1)
        {
            int a = Blk[Q[i].u], b = Blk[Q[i].v], c = Q[i].d;
            while (a != b)
            {
                if (dep[a] > dep[b]) swap(a, b);
                dis[b] = min(dis[b], c), b = pre[b];
            }
        }
        res = 0, Cal(1, 0), ans = max(ans, res);
        end : continue;
    }
    printf("%lld\n", ans);
    return 0;
}