BZOJ1808 [IOI2007]Training 训练路径

前言

又切了一道IOI的题…

分析

题目要求我们删去一些边,使得图中不存在偶环。
我们可以从简单的情况开始考虑,先考虑只有一条是非树边的环,如果它连接的树边长是奇数,那么它必不能保留。
这时候“简单(偶)环”就被排除了,接下来考虑复杂的环,这时候图中剩下的只有简单奇环,当两个奇环通过一条(或多条奇数边)重合在一起,我们将重复的边删去,就构成偶环了。
所以我们可以知道最终我们要留下的是一颗奇环仙人掌。这里解释一下仙人掌是什么意思:

仙人掌是不含自环的,一条边最多属于一个简单环的无向连通图.
从定义不难看出树其实也是仙人掌的一种。

这时候问题就转化为了删去代价和最小的边得到一个奇环仙人掌,我们再将问题转化一下,就变成:求一颗边权和最大的奇环仙人掌。
观察到题目中强调一个点最多只连10条边,因此考虑状压DP.
我们设DP[u][S]表示以u为根的子树,还没有考虑过S集合中的子节点的最大边权和,最终答案就是DP[1][0]。对于非树边,为了避免重复,我们将它的代价累加到两个端点的lca计算。初始时,不考虑连向子节点的边在环上,那么DP[u][S]=\sum DP[v][0]. 然后我们考虑加入环:对于环的贡献,我们不好直接转移,不过数据规模较小,可以暴力计算。我们从那条非树边两个端点暴力向上爬,爬到当前节点v,我们累加的就是DP[v][\lbrace son\rbrace ].(son表示爬上来的子节点,即爬上来的那条边未考虑(在环上)的最大边权和)
最后我们枚举不含有这个环上来的边的状态,更新新的状态就可以了。

参考程序

typedef std::vector<int> Vec;
typedef int Arr[MAXN];

struct TEdge {
    int to, next;
} E[MAXN << 1];
struct Edge {
    int u, v, c;
} ee[MAXM];

int N, M, tote, totnt, totc, F[MAXN][Lg_N], DP[MAXN][(1 << 10) + 10];
Arr last, dep, sid;
Vec crs[MAXN];

inline void add_edge(int u, int v) {
    E[++tote] = (TEdge){v, last[u]}, last[u] = tote;
    E[++tote] = (TEdge){u, last[v]}, last[v] = tote;
}

int main() {
    using FastIO::read;

    read(N), read(M);
    for (int i = 0, a, b, c; i < M; i++) {
        read(a), read(b), read(c);
        if (!c) add_edge(a, b);
        else ee[totnt++] = (Edge){a, b, c}, totc += c;
    }

//  预处理dfs
    dfs1(1);

    for (int i = 0; i < totnt; i++) {
        Edge & e = ee[i];
        int l = lca(e.u, e.v), len = dep[e.u] + dep[e.v] - (dep[l] << 1);
//      将有用的非树边计入
        if (len & 1 ^ 1) crs[l].pb(i);
    }
    dfs2(1);

    printf("%d\n", totc - DP[1][0]);
    return 0;
}

void dfs1(int u) {
    for (int i = 1; i < Lg_N && F[u][i - 1]; i++) F[u][i] = F[F[u][i - 1]][i - 1];
    for (int v, e = last[u]; e; e = E[e].next) {
        if ((v = E[e].to) == F[u][0]) continue;
        dep[v] = dep[u] + 1, F[v][0] = u;
        dfs1(v);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v);
//  发现lca尝试新写法常年打挂,还是写稳定的增量法吧...
    for (int i = 0, delta = dep[u] - dep[v]; i < Lg_N && (1 << i) <= delta; i++)
        if (delta >> i & 1) u = F[u][i];
    if (u == v) return u;
    for (int i = Lg_N - 1; i >= 0; i--)
        if (F[u][i] != F[v][i]) u = F[u][i], v = F[v][i];
    return F[u][0];
}

void dfs2(int u) {
    Vec son;
    for (int v, e = last[u]; e; e = E[e].next) {
        if ((v = E[e].to) == F[u][0]) continue;
        dfs2(v);
        son.pb(v);
    }
    int totson = son.size();
//  给每个子节点编号,并记录每个点在它父亲处的编号,方便状压
    for (int i = 0; i < totson; i++) sid[son[i]] = i;
    for (int mask = (1 << totson) - 1; mask >= 0; --mask) {
//      初始化状态
        for (int i = 0; i < totson; i++)
            if (mask >> i & 1 ^ 1) DP[u][mask] += DP[son[i]][0];
    }
//  枚举每一条产生贡献的非树边
    for (Vec::iterator it = crs[u].begin(); it != crs[u].end(); ++it) {
        int x = ee[*it].u, y = ee[*it].v, ret = ee[*it].c, 
            s1id = sid[x], s2id = sid[y];
        if (x != u) {
            ret += DP[x][0];
            for (; F[x][0] != u; x = F[x][0]) ret += DP[F[x][0]][1 << sid[x]];
//          找到环是那一条边
            if (F[x][0] == u) s1id = sid[x];
        }
        if (y != u) {
            ret += DP[y][0];
            for (; F[y][0] != u; y = F[y][0]) ret += DP[F[y][0]][1 << sid[y]];
            if (F[y][0] == u) s2id = sid[y];
        }
        x = ee[*it].u, y = ee[*it].v;
//      我们枚举一个要更新到的状态,那么之前的状态就是环上的边未考虑的状态
        for (int mask = 0, lmt = 1 << totson; mask < lmt; ++mask) {
            int prf = mask;
            if (x ^ u) {
                if (mask >> s1id & 1) continue;
//              注意这里只有x不是u我们才能把1<<s1id压入状态
//              否则压入的元素是无效的,还会产生奇怪的错误
                prf |= 1 << s1id;
            }
            if (y ^ u) {
                if (mask >> s2id & 1) continue;
                prf |= 1 << s2id;
            }
            DP[u][mask] = std::max(DP[u][mask], DP[u][prf] + ret);
        }
    }
}

总结

这题分析出图的最后形态很重要,可以大大简化问题。以后剖析问题还是应该从简入手。另外,这个状压DP也比较转移。程序细节也较多。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注