[Solution]APIO2013道路费用ORZ题解报告

比较呵呵地ORZ了标程,然后写了一天。。= =果然蒟蒻。

就简要地说一下做法吧。。

首先,为了保证新的K条边优先加入生成树,先对这K条边连接的点进行集合合并。(不加任何边)

构建一张图G备用。

其次,按照费用从小到大的顺序插入所有的原来的边,如果当前这条边连接了两个原来分离的集合,就在G中加一条和原来相同的边,并合并集合。

这样做之后,可以注意到实际插入的边是一棵生成树,但由于K条边没有在G中加入,因此G中实际上是若干个分离的连通分量。

对原来的边进行处理,只有两个端点在不同的连通分量中的边,他才是有用的,否则,他不可能出现在下述的任何一棵生成树中,而是在一个连通分量内,不必考虑。

于是对这些连通分量缩点,计算出总人数。

由于K很小,暴力枚举K条边在最终生成树中的二进制状态。对于每一个状态,(现在的G图是孤立的点组成的图),首先加入K条边,并合并集合,再按照费用从小往大的顺序加入原来的边,直到形成以原来标号为1的点所在的连通分量缩成的点为根的一棵树。此时,我们显然需要使得这棵树成为此时选取状态下的最小生成树,再计算答案就可以了。不过,这需要我们合理地确定K条边的费用,如何确定呢?在形成的树中进行DFS计算出以某一个点为根的子树的总人数,再记录下每个点的在树中的深度。枚举K条边,这条边走过的人数显然是这条边的一个深度较大端点为根的子树的总人数值。那么关键是这条边的费用。我们按照费用由小到大枚举那些刚才没有被选入生成树中的有用边,如果他的两个端点是否在K条边中这条边深度较大端点为根的子树中的状态不同,证明这条边在在K条边中这条边所包含在的一个环中。那么,只要让这条边的费用与他相同,就能保证这条边不会被替换了。对于每个状态,用K条边费用与总人数乘积的和来更新答案。

累死了。。。上BZOJ RANK2代码...

/**************************************************************
    Problem: 3206
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:4164 ms
    Memory:15188 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
inline char getc() {
    static const int L = 1 << 16;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
typedef long long LL;
#define N (100010)
#define M (300010)
#define K (25)
struct Edge_Weigh {
    int from , to , weigh;
    void read() {
        from = getint();
        to = getint();
        weigh = getint();
    }
    bool operator < (const Edge_Weigh &b) const {
        return weigh < b.weigh;
    }
}EW[M] , between[M] , tmp[M];
struct Edge_Extra {
    int from , to;
    void read() {
        from = getint();
        to = getint();
    }
}EE[K];
int person[N];
int pa[N];
int stack[N] , top;
int find(int x) {
    if (x == pa[x])
        return x;
    for(; x != pa[x] ; x = pa[x])
        stack[++top] = x;
    while(top--)
        pa[stack[top]] = x;
    return x;
}
int head[N] , next[N << 1] , end[N << 1] , ind;
void addedge(int a , int b) {
    int q = ++ind;
    next[q] = head[a];
    head[a] = q;
    end[q] = b;
}
int cnt;
LL totperson[K];
int use[K] , two[K] , size_use;
void pre(int x , int label) {
    pa[x] = label;
    totperson[label] += person[x];
    for(int j = head[x] ; j ; j = next[j])
        if (!pa[end[j]])
            pre(end[j] , label);
}
int depth[K] , mask[K];
LL all[K];
void dfs(int x , int fa) {
    mask[x] = two[x];
    all[x] = totperson[x];
    for(int j = head[x] ; j ; j = next[j]) {
        if (end[j] != fa) {
            depth[end[j]] = depth[x] + 1;
            dfs(end[j] , x);
            all[x] += all[end[j]];
            mask[x] |= mask[end[j]];
        }
    }
}
int main() {
    int n , m , add;
    n = getint();
    m = getint();
    add = getint();
    int i , j;
    for(i = 1 ; i <= m ; ++i)
        EW[i].read();
    for(i = 1 ; i <= add ; ++i)
        EE[i].read();
    for(i = 1 ; i <= n ; ++i)
        person[i] = getint();
    sort(EW + 1 , EW + m + 1);
    for(i = 1 ; i <= n ; ++i)
        pa[i] = i;
    for(i = 1 ; i <= add ; ++i)
        if (find(EE[i].from) != find(EE[i].to))
            pa[pa[EE[i].from]] = pa[EE[i].to];
    for(i = 1 ; i <= m ; ++i) {
        if (find(EW[i].from) != find(EW[i].to)) {
            addedge(EW[i].from , EW[i].to);
            addedge(EW[i].to , EW[i].from);
            pa[pa[EW[i].to]] = pa[EW[i].from];
        }
    }
    for(i = 1 ; i <= n ; ++i)
        pa[i] = 0;
    for(i = 1 ; i <= n ; ++i)
        if (!pa[i])
            pre(i , ++cnt);
    int root = pa[1];
    for(i = 1 ; i <= m ; ++i) {
        EW[i].from = pa[EW[i].from];
        EW[i].to = pa[EW[i].to];
    }
    for(i = 1 ; i <= add ; ++i) {
        EE[i].from = pa[EE[i].from];
        EE[i].to = pa[EE[i].to];
    }
    for(i = two[0] = 1 ; i <= cnt ; ++i)
        two[i] = two[i - 1] << 1 , pa[i] = i;
    int size_between = 0;
    for(i = 1 ; i <= m ; ++i)
        if(pa[EW[i].from] != pa[EW[i].to]) {
            pa[pa[EW[i].from]] = pa[EW[i].to];
            between[++size_between] = EW[i];
        }
    LL ans = 0;
    for(int S = 1 ; S < two[add] ; ++S) {
        ind = 0;
        memset(head , 0 , (cnt+1)*sizeof(int));
        for(i = 1 ; i <= cnt ; ++i)
            pa[i] = i;
        size_use = 0;
        int size_tmp = 0;
        for(i = 1 ; i <= add ; ++i)
            if ((S & two[i - 1]) && find(EE[i].from) != find(EE[i].to)) {
                use[++size_use] = i;
                addedge(EE[i].from , EE[i].to);
                addedge(EE[i].to , EE[i].from);
                pa[pa[EE[i].to]] = pa[EE[i].from];
            }
        for(j = 1 ; j <= size_between ; ++j)
            if (find(between[j].from) != find(between[j].to)) {
                addedge(between[j].from , between[j].to);
                addedge(between[j].to , between[j].from);
                pa[pa[between[j].from]] = pa[between[j].to];
            }
            else
                tmp[++size_tmp] = between[j];
        dfs(root , depth[root] = 0);
        LL now = 0;
        for(i = 1 ; i <= size_use ; ++i) {
            int a = depth[EE[use[i]].from]>depth[EE[use[i]].to]?EE[use[i]].from:EE[use[i]].to;
            for(j = 1 ; j <= size_tmp ; ++j) {
                if ((!(mask[a]&two[tmp[j].from]))^(!(mask[a]&two[tmp[j].to]))) {
                    now += (LL)tmp[j].weigh * all[a];
                    break;
                }
            }
        }
        if (now > ans)
            ans = now;
    }
    printf("%lld" , ans);
    return 0;
}
comments powered by Disqus