首页 > 其他 > 详细

[bzoj1369][Baltic2003]Gem_树形dp_结论题

时间:2018-07-21 23:49:32      阅读:57      评论:0      收藏:0      [点我收藏+]

标签:结论题   颜色   sans   string   pan   int   brush   while   using   

Gem bzoj-1369 Baltic-2003

题目大意:给你一棵树,让你往节点上添自然数,使得任意相邻节点的数不同且使得权值最小。

注释:n为结点个数,$1\le n\le 10^3$。

想法:呵呵,学长一直在骂结论题,我一直觉得没啥.. ...

知道tm碰见这玩意儿,卧槽?!

树上相邻节点不同色,颜色个数最小值至多为logn。

最后,附上丑陋的代码... ...

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#define ll long long 
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
int n,cnt;
int last[10005],f[10005][25];
struct edge
{
	int to,next;
}e[20005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void dp(int x,int fa)
{
	for(int j=1;j<=20;j++)
		f[x][j]=j;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
			dp(e[i].to,x);
	for(int j=1;j<=20;j++)
	{
		for(int i=last[x];i;i=e[i].next)
			if(e[i].to!=fa)
			{
				int mn=inf;
				for(int k=1;k<=20;k++)
					if(j!=k)mn=min(mn,f[e[i].to][k]);
				f[x][j]+=mn;
			}
	}
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	dp(1,0);
	int ans=inf;
	for(int i=1;i<=20;i++)
		ans=min(ans,f[1][i]);
	printf("%d\n",ans);
	return 0;
}

小结:多做一些结论题吧... ...

[bzoj1369][Baltic2003]Gem_树形dp_结论题

标签:结论题   颜色   sans   string   pan   int   brush   while   using   

原文:https://www.cnblogs.com/ShuraK/p/9348447.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号