[Ioi2007]training 训练路径

我们是从来不放网上的题目的,某神仙说过…..

(然后,啪啪啪,打脸)

题意:

马克(Mirko)和斯拉夫克(Slavko)正在为克罗地亚举办的每年一次的双人骑车马拉松赛而紧张训练。他们需要选择一条训练路径。
他们国家有N个城市和M条道路。每条道路连接两个城市。这些道路中恰好有N-1条是铺设好的道路,其余道路是未经铺设的土路。幸运的是,每两个城市之间都存在一条由铺设好的道路组成的通路。换句话说,这N个城市和N-1条铺设好的道路构成一个树状结构。
此外,每个城市最多是10条道路的端点。
一条训练路径由某个城市开始,途经一些道路后在原来起始的城市结束。因为马克和斯拉夫克喜欢去看新城市,所以他们制定了一条规则:绝不中途穿越已经去过的城市,并且绝不在相同的道路上骑行两次(不管方向是否相同)。训练路径可以从任何一个城市开始,并且不需要访问所有城市。
显然,坐在后座的骑行者更为轻松,因为坐在前面的可以为他挡风。为此,马克和斯拉夫克在每个城市都要调换位置。为了保证他们的训练强度相同,他们要选择一条具有偶数条道路的路径。
马克和斯拉夫克的竞争者决定在某些未经铺设的土路上设置路障,使得他们两人不可能找到满足上述要求的训练路径。已知在每条土路上设置路障都有一个费用值(一个正整数),并且竞争者不能在铺设好的道路上设置路障。

任务:

给定城市和道路网的描述,写一个程序计算出为了使得满足上述要求的训练路径不存在,而需要的设置路障的最小总费用。

输入格式:

输入的第一行包含两个整数NM(2≤N≤1000,N-1≤M≤5000),分别表示城市和道路的个数。

接下来的M行每行包含3个整数A,BC (1≤A≤N, 1≤B≤N, 0≤C≤10 000), 用来描述一条道路。AB是不同的整数,表示由这条道路直接相连的两个城市。对于铺设好的道路C0;对于土路,C是在该条路上设置路障所需的费用值。

每个城市最多是10条道路的端点。任意两个城市都不会有多于一条直接相连的道路。

输出格式

输出包含一个整数,表示求出的最小总费用。

分析:

我们已知我们已经建好整棵树,然后我们加入假边时,可以肯定,如果这条边在树上构成一个偶数简单环,那么这条边永远没有可能加入…..同时,如果两个环公用两个以上的点,那么尽管这两个环是奇环,可是他们的相交会导致无论如何都可以拼出小环……最后得出结论,最后的图是一个奇环仙人掌!!!!
然后我们要用最小代价找出最小的代价让图变成奇环仙人掌,反过来想,我们只要找到这个最大代价的奇环仙人掌,用总和减一减,就是答案…..
但是怎么求这个仙人掌的最大代价呢……
我们考虑DP,我们设计数组dp[i][j],i表示这是哪个点,j表示他的哪些儿子我们不考虑,意思就是我们只思考除了j中含有的以外的儿子产生的代价…..(因为一个点儿子非常少,所以我们这样考虑)
然后我们思考怎么转移….先来看官方的一组图片……

可以看出,我们可以在树上面枚举环,然后把环抠出来,然后加上被拆开的剩下的图的代价……
比如我们现在看一条假边x,y,他们的lcaLca_{xy}(我们为了方便统计,我们把环的贡献加到Lca上),他与树边连成了一个环,我们考虑怎么统计答案…..
假设x不是Lca_{xy},然后我们易得,这个点的整个子树的代价可以加到cost里面统计答案…..
由于他的子树里面都是可以考虑的边,所以先加上dp[x][0]…….
然后我们从x点往上面跳,直到成为Lca_{xy}的儿子,然后我们对于每一个点,假设他是从第k个儿子跳上来了,那么我们就给cost 加上dp[x][1 << k-1]的代价,然后我们把答案统计到根上…..
我们考虑,有状态dp[x][s],他是从dp[x][s|son_x|son_y]上转移来的,就好了…..
看不懂可以提问,因为评论要审核所以我会认真看的……

代码:

%%%acheing

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define LL long long
#define P pair<int, int>
const LL N = 1e3 + 10;
const LL mod = 1e4 + 7;
const LL inf = 0x3f3f3f3f;
using namespace std;
template <typename tp>
inline void read(tp &x)
{
    x = 0;char c = getchar();bool f = 0;
    for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
int n, m, ans;
int tree_head[N], tree_cnt;
struct Tree_Edge {int next, to;} tree_edge[N * 10];
inline void add(int from, int to)
{
    tree_edge[++tree_cnt].next = tree_head[from];
    tree_edge[tree_cnt].to = to;
    tree_head[from] = tree_cnt;
}
int cnt, fa[N][15], dep[N], du[N], dp[N][1 << 12];
struct Edge {int from, to, cost;} edge[N * 10];
vector<int> vec[N];
void dfs_init(int now, int fath)
{
    fa[now][0] = fath; dep[now] = dep[fath] + 1;
    for (int i = 1; i <= 12; i++) fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for (int i = tree_head[now]; i; i = tree_edge[i].next)
    {
        int to = tree_edge[i].to;
        if (to == fath) continue;
        du[now]++;dfs_init(to, now);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 12; i >= 0; i--) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = 12; i >= 0; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
int son[N][12], son_fan[N];
void dfs_dp(int now)
{
    for (int i = tree_head[now]; i; i = tree_edge[i].next) if (fa[now][0] != tree_edge[i].to) dfs_dp(tree_edge[i].to);
    int son_cnt = 0;
    for (int i = tree_head[now]; i; i = tree_edge[i].next) if (fa[now][0] != tree_edge[i].to) son[now][++son_cnt] = tree_edge[i].to, son_fan[tree_edge[i].to] = son_cnt;
    for (int i = 0; i < (1 << du[now]); i++)
        for (int j = 1; j <= du[now]; j++)
            if (!(i & (1 << j - 1)))
                dp[now][i] += dp[son[now][j]][0];
    int siz = vec[now].size();
    for (int i = 0; i < siz; i++)
    {
        int from = edge[vec[now][i]].from,
        to = edge[vec[now][i]].to, cost = edge[vec[now][i]].cost;
        int L = son_fan[from], R = son_fan[to];
        if (from != now)
        {
            cost += dp[from][0];
            while (fa[from][0] != now)
            {
                int fath = fa[from][0];
                cost += dp[fath][1 << son_fan[from] - 1];
                if (fa[fath][0] == now) L = son_fan[fath];
                from = fath;
            }
        }
        if (to != now)
        {
            cost += dp[to][0];
            while (fa[to][0] != now)
            {
                int fath = fa[to][0];
                cost += dp[fath][1 << son_fan[to] - 1];
                if (fa[fath][0] == now) R = son_fan[fath];
                to = fath;
            }
        }
        from = edge[vec[now][i]].from, to = edge[vec[now][i]].to;
        for (int j = 0; j < 1 << du[now]; j++)
        {
            int res = j;
            if (from != now)
            {
                if (res & (1 << L - 1)) continue;
                res |= 1 << L - 1;
            }
            if (to != now)
            {
                if (res & (1 << R - 1)) continue;
                res |= 1 << R - 1;
            }
            dp[now][j] = max(dp[now][j], cost + dp[now][res]);
        }
    }
}
signed main()
{
    read(n), read(m);
    for (int i = 1, u, v, c; i <= m; i++)
    {
        read(u), read(v), read(c);
        if (!c) add(u, v), add(v, u);
        else edge[++cnt] = (Edge){u, v, c};
        ans += c;
    }
    dfs_init(1, 1);
    for (int i = 1; i <= cnt; i++)
    {
        int Lca = lca(edge[i].from, edge[i].to);
        int dis = dep[edge[i].from] + dep[edge[i].to] - 2 * dep[Lca];
        if (!(dis & 1)) vec[Lca].push_back(i);
    }
    dfs_dp(1);
    printf("%d\n", ans - dp[1][0]);
    return 0;
}

关于“[Ioi2007]training 训练路径”我的3个想法

    1. 就是说,我们反着考虑,最后得到的值是dp[x][0],那么我们考虑这个环经过的边是当前点和son_x和son_y连得边,我们现在统计了使用该环的代价,这两条边都不能用了,然后我们要找到可行的除了这两条边的dp状态,去更新这两条边未考虑的状态…..

发表评论

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