Problem

http://uoj.ac/problem/108

Solution

先把必须加入的边缩起来，将图的范围大大缩小。

然后考虑不一定要加入的边。这里有一个很重要的优化，即不一定要加入的边也以最小生成树的形式覆盖一定要加入的边。非最小生成树形式的边可以直接不考虑。这部分可以看代码理解——直接让边的数目变成 $k$ 级别的。

枚举必须加入的边，再缩图，再考虑每条边的最大值，再算贡献即可。

复杂度：$O(m\log m +2^kk^2)$

Code

// Code by ajcxsu
// Problem: road cost

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
#define INF (0x3f3f3f3f)
typedef long long ll;
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=ch=='-', ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=2e5+10, M=4e5+10, K=23;
int h[K], to[M], nexp[M], W[M], p=1;
inline void ins(int a, int b) { if(a==b) return; nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=INF, p++; }
int e[K][K];
struct Edge { int u, v, w; char ok; } ed[M], sp[K];
bool cmp(const Edge &a, const Edge &b) { return a.w<b.w; }

int fa[N], rk[N];
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }
extern inline bool Union(int a, int b) {
    int af=Find(a), bf=Find(b); if(af==bf) return false;
    if(rk[af]>rk[bf]) swap(af, bf);
    return rk[bf]=max(rk[af]+1, rk[bf]), fa[af]=bf, true;
}

ll c[N], c2[K];
char chose[K];

int n, m, k, idx, rt;
int fr[K], fru[K], dep[K];
void cov(int x, int y, int d) {
    if(dep[x]<dep[y]) swap(x, y);
    while(dep[x]>dep[y]) {
        W[fru[x]]=W[fru[x]^1]=min(W[fru[x]], d);
        x=fr[x];
    }
    while(x!=y) {
        W[fru[x]]=W[fru[x]^1]=min(W[fru[x]], d);
        W[fru[y]]=W[fru[y]^1]=min(W[fru[y]], d);
        x=fr[x], y=fr[y];
    }
}
void dfs2(int x, int k) {
    dep[x]=k;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr[x]) {
            fr[to[u]]=x, fru[to[u]]=u;
            dfs2(to[u], k+1);
            c2[x]+=c2[to[u]];
        }
}
ll ans=0;
int rid[K];
void dfs(int x) {
    if(x==k) {
        assert(idx<K);
        memset(fa, 0, sizeof(int)*(K));
        memset(rk, 0, sizeof(int)*(K));
        for(int i=0;i<k;i++)
            if(chose[i]) if(!Union(sp[i].u, sp[i].v)) return;
        CLR(h, 0), p=2;
        for(int i=0;i<m;i++)
            if(Union(ed[i].u, ed[i].v)) ed[i].ok=1;
            else ed[i].ok=0;
        memset(fa, 0, sizeof(int)*(K));
        memset(rk, 0, sizeof(int)*(K));
        for(int i=0;i<m;i++)
            if(ed[i].ok) Union(ed[i].u, ed[i].v);
        CLR(c2, 0);
        for(int i=1;i<=idx;i++) if(!fa[i]) rid[i]=i;
        for(int i=1;i<=idx;i++) rid[i]=rid[Find(i)];
        #define Find(x) rid[x]
        for(int i=1;i<=idx;i++) c2[Find(i)]+=c[i];
        for(int i=k-1;i>=0;i--)
            if(chose[i])
                ins(Find(sp[i].u), Find(sp[i].v)), ins(Find(sp[i].v), Find(sp[i].u));
        fru[Find(rt)]=fr[Find(rt)]=0, dfs2(Find(rt), 1);
        for(int i=0;i<m;i++) if(!ed[i].ok) cov(Find(ed[i].u), Find(ed[i].v), ed[i].w);
        #undef Find
        ll tot=0;
        for(int i=1;i<=idx;i++) if(!fa[i]) tot+=c2[i]*W[fru[i]];

        ans=max(ans, tot);
    }
    else {
        chose[x]=1;
        dfs(x+1);
        chose[x]=0;
        dfs(x+1);
    }
}

int main() {
    // clock_t begin=clock();
    CLR(e, 0x3f);
    gn(n), gn(m), gn(k);
    int u, v, w;
    for(int i=0;i<m;i++) gn(u), gn(v), gn(w), ed[i]={u, v, w};
    for(int i=0;i<k;i++) gn(u), gn(v), sp[i]={u, v};
    for(int i=0;i<k;i++) Union(sp[i].u, sp[i].v);
    sort(ed, ed+m, cmp);
    for(int i=0;i<m;i++) if(Union(ed[i].u, ed[i].v)) ed[i].ok=1;
    CLR(fa, 0);
    CLR(rk, 0);
    for(int i=0;i<m;i++) if(ed[i].ok) Union(ed[i].u, ed[i].v);
    int mp[N];
    for(int i=1;i<=n;i++) if(!fa[i]) mp[i]=++idx;
    for(int i=1;i<=n;i++) mp[i]=mp[Find(i)];
    CLR(fa, 0), CLR(rk, 0);
    for(int i=0;i<m;i++) if(!ed[i].ok) {
        u=mp[ed[i].u], v=mp[ed[i].v];
        if(Union(u, v)) e[u][v]=e[v][u]=min(e[u][v], ed[i].w);
    }
    m=0;
    for(int i=1;i<=idx;i++)
    for(int j=i+1;j<=idx;j++)
        if(e[i][j]!=INF) ed[m++]={i, j, e[i][j], 0};
    sort(ed, ed+m, cmp);
    for(int i=0;i<k;i++) sp[i].u=mp[sp[i].u], sp[i].v=mp[sp[i].v];
    for(int i=1;i<=n;i++) gn(w), c[mp[i]]+=w;
    rt=mp[1];
    dfs(0);
    printf("%lld\n", ans);
    return 0;
}