M_sea

洛谷4395 [BOI2003]Gem 气垫车
LuoguBZOJ分析设 $f[u][i]$ 表示子树 $u$ 中, $u$ 填 $i$ 的最小权值和。转移直接枚...
扫描右侧二维码阅读全文
21
2019/05

洛谷4395 [BOI2003]Gem 气垫车

Luogu

BZOJ

分析

设 $f[u][i]$ 表示子树 $u$ 中, $u$ 填 $i$ 的最小权值和。

转移直接枚举子节点即可。

然后可以证明颜色数最多 $\log n$ ,但是 $3$ 都能过???

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;
const int C=10;

struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int f[N][C+10];

inline void dfs(int u,int fa) {
    for (re int i=1;i<=C;++i) f[u][i]=i;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        for (re int j=1;j<=C;++j) {
            int mn=2e9;
            for (re int k=1;k<=C;++k)
                if (k!=j) mn=min(mn,f[v][k]);
            f[u][j]+=mn;
        }
    }
}

int main() {
    int n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    int ans=2e9;
    for (re int i=1;i<=C;++i) ans=min(ans,f[1][i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 10 PM

2 条评论

  1. smy

    为什么颜色数不是2啊
    /ts

    1. M_sea
      @smy

      但是有的时候 2 并不是最优的...(事实上 2 只有 20 分)

发表评论