BZOJ 1369: [Baltic2003]Gem(树形dp)

解题思路

　　直接按奇偶层染色是错的，\(WA\)了好几次，所以要树形\(dp\)，感觉最多\(log\)种颜色，不太会证。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=10005;

inline int rd(){

    int x=0,f=1; char ch=getchar();

    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return f?x:-x;

}

int n,head[N],cnt,to[N<<1],nxt[N<<1];

int f[N][30],ans=1e9;

inline void add(int bg,int ed){

    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

void dfs(int x,int F){

    for(int i=head[x];i;i=nxt[i]){

        int u=to[i]; if(u==F) continue;

        dfs(u,x);

    }

    for(int i=1;i<=25;i++){

        f[x][i]=i;

        for(int j=head[x];j;j=nxt[j]){

            int u=to[j],Min=1e9; if(u==F) continue;

            for(int k=1;k<=25;k++)

                if(k!=i) Min=min(Min,f[u][k]);

            f[x][i]+=Min;

        }

    }

}	

int main(){

    n=rd(); int x,y;

    for(int i=1;i<n;i++){

        x=rd(); y=rd();

        add(x,y); add(y,x);

    }

    dfs(1,0);

    for(int i=1;i<=25;i++) ans=min(ans,f[1][i]);

    printf("%d\n",ans);

    return 0;

}

巴特西

BZOJ 1369: [Baltic2003]Gem(树形dp)

解题思路

代码

最新文章

热门文章