IOI2007 training

题意

树上有m条非树边, 删除且仅删除一些非树边, 代价为c_i

问删边的最小代价使最后树上不存在偶环

分析

  • 很直接知道要删去本身形成长度为偶的环

不需要lca的辅助, 可以直接判断非树边连接两点的深度奇偶性即可

  • 研究奇环

发现对于单个奇环来说并不会对答案造成任何影响(即可以保留)

但是如果2个奇环有交集, 那么一定可以通过一种走法形成偶环, 构造如下:

设交点左右端点分别为u,v. 可以走 环一 从uv, 再从环二从vu 即可形成偶环

补集转换, 即求出可以保留最多的环, 使得它们不相交且\sum c_i 最大

考虑每一条边在它的lca处考虑, 设当前至u

  1. 不将任何lcau的边加入, 答案即为\sum_{v\in son_u}f_v
  2. 加入lcau的边

像图例3中的情况一样的解法:

  • 由于每一条边最多被奇环覆盖一次, 所以这也是为什么分开的部分可以单独考虑, 不需要考虑之间的连边, 否则一定在路径上有边被覆盖了2次以上!

那么我们只要状压dp:

dp[u][S], u表示当前节点, S表示孩子节点的状态: 0表示可取, 1表示不可取(即当做没有该点)

答案就是dp[1][0]

假设有dp[u][a,b,c,d,e]考虑加入了一条边x-y,x 至u的路径上次于u的点为a(即u与a为父子关系), yb

可以有转移方程
dp[u][a,b,c,d,e]=max\ of \ calc(x, y) + dp[u][c,d,e]
calc(x,y)表示w(x-y)+分解路径上点的答案, 就如图上分开的部分的答案

详见代码

Code

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 1E3 + 50;

int n, m, tot, id[N], f[N], dep[N], dp[N][1 << 10 | 50];
struct edge {
    int u, v, c;
    edge(int u, int v, int c) : u(u), v(v), c(c) {}
};
vector<int> g[N];
vector<edge> line[N], q;

inline void add(int u, int v) {
    g[u].push_back(v), g[v].push_back(u);
}
inline void Max(int &u, int v) {
    if(v > u) u = v;
}
void bdfs(int u, int fa) {
    f[u] = fa, dep[u] = dep[fa] + 1;
    for(int i = 0, v; i < (int) g[u].size(); ++i) {
        v = g[u][i];
        if(v == fa) continue;
        id[v] = i, bdfs(v, u);
    } 
}
int lca(int u, int v) {
    for(; u != v; u = f[u]) 
        if(dep[u] < dep[v]) swap(u, v);
    return u;
}
void init() {
    bdfs(1, 1);
    for(auto e : q) {
        tot += e.c;
        if((dep[e.u] & 1) ^ (dep[e.v] & 1)) continue;
        line[lca(e.u, e.v)].push_back(e);
    }
} 
int calc(int u, int v) {
    int res = 0, nex = 0;
    while(u != v) {
        res += dp[u][nex];
        nex = 1 << id[u], u = f[u];
    }
    return res;
}
void dfs(int u) {
    int sz = g[u].size();
    vector<edge> getn; 
    for(auto v : g[u]) if(v != f[u]) dfs(v);
    // init_part()
    for(int i = 0; i < (1 << sz); ++i) 
        for(int j = 0; j < sz; j++) 
            if(!(i >> j & 1)) dp[u][i] += dp[g[u][j]][0];
    for(auto e : line[u]) {
        int eu = e.u, ev = e.v, l1 = 0, l2 = 0;
        for(; eu != u; eu = f[eu]) l1 = eu;
        for(; ev != u; ev = f[ev]) l2 = ev;
        getn.push_back(edge(l1, l2, calc(e.u, u) + calc(e.v, u) + e.c));
    }
    for(auto e : getn) {
        int iu = id[e.u], iv = id[e.v];
        if(!e.u) iu = -1; 
        else if(!e.v) iv = -1, swap(iu, iv);        for(int i = 0; i < (1 << sz); ++i) {
            if(iu > -1 && !(i >> iu & 1) && !(i >> iv & 1)) Max(dp[u][i], dp[u][(i | (1 << iu)) | (1 << iv)] + e.c);
            else if(iu < 0 && !(i >> iv & 1)) Max(dp[u][i], dp[u][i | (1 << iv)] + e.c);
        }
    }
}
int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v, c; i <= m; i++) {
         scanf("%d%d%d", &u, &v, &c);
         if(c) q.push_back(edge(u, v, c));
         else add(u, v);
    }
    init();
    dfs(1);
    printf("%d\n", tot - dp[1][0]);
    return 0;
}

One Reply to “IOI2007 training”

发表评论

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