BZOJ3206: [Apio2013]道路费用

bzoj3206.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
const int M = 300000 * 2 + 9,N = 100000 + 9;
struct Edge
{
    int x,y,c;
}et[M],en[M],eo[M];
inline bool operator<(const Edge &lhs,const Edge &rhs){return lhs.c < rhs.c;}
int n,m,K,Map[N],p[N],num[N],fa[N],edge[N],cnt,val[N],root,d,depth[N],fa_edge[N];
int son[N],lnk[N * 2],nxt[N * 2],ec,wei[N * 2],F[N],Time,In[M],tmp[N];
long long sz[N],size[N];
int getf(int x)
{
    for (; F[x] != x; x = F[x]) tmp[++tmp[0]] = x;
    while (tmp[0]) F[tmp[tmp[0]--]] = x;
    return F[x];
}
void MST(Edge (&a)[M],int m)
{
    ++Time;
    for (int i = 1; i <= n; ++i) F[i] = i;
    for (int i = 1; i <= m; ++i) {
        int fx = getf(a[i].x),fy = getf(a[i].y);
        if (fx == fy) continue;
        In[i] = Time;
        F[fy] = fx;
    }
}
inline void addedge(int x,int y,int z)
{
    nxt[++ec] = son[x];
    son[x] = ec;
    lnk[ec] = y;
    wei[ec] = z;
}
inline void Addedge(int x,int y,int z){addedge(x,y,z);addedge(y,x,z);}
void reduce()
{
    MST(eo,m);
    int tmp = 0;
    for (int i = 1; i <= m; ++i)
        if (In[i] == Time) eo[++tmp] = eo[i];
    m = tmp;
    for (int i = K + 1; i <= K + m; ++i)
        en[i] = eo[i - K];
    MST(en,K + m);
    tmp = 0;
    int t1 = 0;
    for (int i = K + 1; i <= K + m; ++i)
        if (In[i] == Time) eo[++tmp] = en[i];
        else et[++t1] = en[i];
    MST(eo,tmp);
    m = 0;
    for (int i = 1; i <= t1; ++i)
        eo[++m] = et[i];
}
void init_ev()
{
    for (int i = 1; i <= K; ++i) {
        en[i].x = Map[getf(en[i].x)];
        en[i].y = Map[getf(en[i].y)];
    }
    for (int i = 1; i <= m; ++i) {
        eo[i].x = Map[getf(eo[i].x)];
        eo[i].y = Map[getf(eo[i].y)];
    }
}
void init_pv()
{
    for (int i = 1; i <= n; ++i) p[++p[0]] = getf(i);
    std::sort(p + 1,p + 1 + n);
    p[0] = std::unique(p + 1,p + 1 + n) - p - 1;
    for (int i = 1; i <= p[0]; ++i) Map[p[i]] = i;
    for (int i = 1; i <= n; ++i) sz[Map[getf(i)]] += num[i];
    root = Map[getf(1)];
}
void dp(int u,int father)
{
    fa[u] = father;
    for (int i = son[u]; i; i = nxt[i]) {
        if (lnk[i] == father) continue;
        depth[lnk[i]] = depth[u] + 1;
        fa_edge[lnk[i]] = wei[i];
        dp(lnk[i],u);
        size[u] += size[lnk[i]];
    }
    size[u] += sz[u];
}
void update(int u,int v,int c)
{
    if (depth[u] < depth[v]) std::swap(u,v);
    for (; depth[u] > depth[v]; u = fa[u])
        if (!et[fa_edge[u]].c && val[fa_edge[u]] > c)
            val[fa_edge[u]] = c;
    for (; u != v; u = fa[u],v = fa[v]) {
        if (!et[fa_edge[u]].c && val[fa_edge[u]] > c)
            val[fa_edge[u]] = c;
        if (!et[fa_edge[v]].c && val[fa_edge[v]] > c)
            val[fa_edge[v]] = c;
    }
}
long long calc(int st)
{
    long long ans = 0;
    int t1 = 0,t2;
    for (int i = 1; i <= K; ++i)
        if ((1 << i - 1) & st) et[++t1] = en[i];
    t2 = t1;
    for (int i = 1; i <= m; ++i) et[++t1] = eo[i];
    MST(et,t1);
    memset(son,0,sizeof(*son) * (n + 1)); ec = 0;
    for (int i = 1; i <= t1; ++i)
        if (In[i] == Time) Addedge(et[i].x,et[i].y,i);
        else if (!et[i].c) return 0;
    memset(size,0,sizeof(*size) * (n + 1));
    dp(root,0);
    for (int i = 1; i <= t2; ++i) val[i] = 0x3f3f3f3f;
    for (int i = t2 + 1; i <= t1; ++i)
        if (In[i] != Time) update(et[i].x,et[i].y,et[i].c);
    for (int i = 1; i <= t2; ++i)
        if (fa[et[i].x] == et[i].y) ans += size[et[i].x] * val[i];
        else ans += size[et[i].y] * val[i];
    return ans;
}
long long work()
{
    n = p[0];
    long long ans = 0;
    for (int i = 1,tot = (1 << K); i < tot; ++i)
        ans = std::max(ans,calc(i));
    return ans;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("3206.in","r",stdin);
    freopen("3206.out","w",stdout);
    #endif
    scanf("%d%d%d",&n,&m,&K);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d",&eo[i].x,&eo[i].y,&eo[i].c);
    std::sort(eo + 1,eo + 1 + m);
    for (int i = 1; i <= K; ++i)
        scanf("%d%d",&en[i].x,&en[i].y);
    for (int i = 1; i <= n; ++i) scanf("%d",num + i);
    reduce();
    init_pv();
    init_ev();
    printf("%lld\n",work());
}