题解 P4649 【[IOI2007] training 训练路径 】

· · 题解

原题地址

官方题解

我的博客

题意概述

给定 n 个点 m 条边的无向图，你需要删掉一些边，使得此图没有长度为偶数的简单环。

删掉第 i 条边有 C_i 的花费，有些边又是不能删的。不能删的边形成图的一棵生成树。

### 思路 对于所有非树边，如果非树边所连接的两个点在树上的距离为奇数，那么会构成一个偶环，删去这些边。 考虑两个仅含有一条非树边的奇环，如果他们在树上的部分有交，那么把两个环合并在一起再去掉那些重复的部分剩下的就一定是一个偶环，所以说我们需要留下一张图，使得没有一条边同时属于两个简单环，也就是一个仙人掌（此处没有考虑在最初就被我们删掉的非树边）。容易证明满足上述条件的方案一定合法。 如果让每条非树边覆盖他连接两点树上的路径上的所有边，那么树上的每一条边最多只能被覆盖一次，再将必须删除的最小边权改为总边权-能留下的最大边权。 因为每个点的度数不超过 10，我们就可以状态压缩。 定义 $f_{(i,S)}$ 为以 $i$ 为根的子树中，不考虑儿子集合 $S$ 的最大边权。 对于一条左右端点$u, v$ 的 $LCA$ 为 $i$ 的非树边， - 如果不选择，此时的 $f_{(i,S)}=\sum_{son\notin S} f_{(son,0)}$； - 如果选择这条边，这条边的贡献 $val$ 分为两个部分： 1. $f_{(u,0)} + f_{(v,0)}
  1. 对于到 LCA 路径上的的每个点 p。设对于 p，不包含 u 或 v 的儿子集合为 K，贡献为 \sum f_{(p,K)}

现在我们可以枚举点 i 的子集 S，令子树包含 u,v 的儿子分别为 x,y。对于 \{ S| x\notin S, y\notin S\}

f_{(i,S)}=\max f_{(i,S|x|y)}+val

最终的答案为总边权减去 f_{(root,0)}。

时间复杂度 \Theta (m2^{10}+mn)。

代码

#include <bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define pb push_back
#define maxn 1010
#define maxm 5010
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn<<1];
struct Brid{
    int from,to,val;
    Brid(int a=0,int b=0,int c=0){
        from=a,to=b,val=c;
    }
}H[maxm];
int head[maxn],p[maxn][12],cnt,n,m;
int dep[maxn],f[maxn][maxn<<2];
int id[maxn],rid[maxn],tot,sum;
std::vector<int>B[maxn];
//H 存储题目给定的所有非树边
//B 存储不构成偶环的边，将它挂在相应的 LCA 处。
void Add(int a=0,int b=0){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void Dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    p[u][0]=fa;
    for (register int i=1;i<12;i++)
    p[u][i]=p[p[u][i-1]][i-1];
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;if (v!=fa) Dfs(v,u);
    }
}
int Lca(int a,int b){
    if (dep[b]<dep[a]) std::swap(a,b);
    for (register int i=11;~i;i--)
        if (dep[p[b][i]]>=dep[a]) b=p[b][i];
    if (a==b) return a;
    for (register int i=11;~i;i--)
        if (p[a][i]!=p[b][i])
        a=p[a][i],b=p[b][i];
    return p[a][0];
}
#define fa(i) (p[i][0])
void Solve(int u){
    int son=0;
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa(u)) continue;
        Solve(v);
    }
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa(u)) continue;
        id[son]=v,rid[v]=1<<son,son++;//id 是儿子编号对应的点，rid 是每个点在父亲处对应的二进制位置
    }
    for (register int S=0,tem=0;S<1<<son;++S,tem=0){
        for (register int i=0;i<son;i++)
            if (!(S>>i&1))
            tem+=f[id[i]][0];
        f[u][S]=tem;
    }//不选择挂在 u 上的非树边。
    for (register int k=B[u].size()-1;~k;--k){
        int i=B[u][k],tem=H[i].val;
        if (H[i].from!=u)
        tem+=f[H[i].from][0];
        if (H[i].to!=u)
        tem+=f[H[i].to][0];
        int a=0,b=0;
        if (H[i].from!=u)
            for (a=H[i].from;fa(a)!=u;a=fa(a))
            tem+=f[fa(a)][rid[a]];
        if (H[i].to!=u)
            for (b=H[i].to;fa(b)!=u;b=fa(b))
            tem+=f[fa(b)][rid[b]];
        for (register int S=0;S<1<<son;++S)
            if ((S&rid[a])==0&&(S&rid[b])==0)
            f[u][S]=max(f[u][S],f[u][S|rid[a]|rid[b]]+tem);
    }
}
#undef fa
int main(){
    scanf("%d%d",&n,&m);
    for (register int i=1,a,b,c;i<=m;++i){
        scanf("%d%d%d",&a,&b,&c);
        if (!c) Add(a,b),Add(b,a);
        else H[++tot]=Brid(a,b,c),sum+=c;
    }
    Dfs(1,0);
    for (register int i=1;i<=tot;++i){
        int t=Lca(H[i].from,H[i].to);
        if (!((dep[H[i].from]+dep[H[i].to]-2*dep[t])&1))
        B[t].pb(i);
    }
    Solve(1);
    printf("%d",sum-f[1][0]);
    return 0;
}