【BZOJ-1369】Gem 树形DP
2024-10-11 22:05:39
1369: [Baltic2003]Gem
Time Limit: 2 Sec Memory Limit: 64 MB
Submit: 282 Solved: 180
[Submit][Status][Discuss]
Description
给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。
Input
先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连
Output
最小的总权值
Sample Input
10
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3
Sample Output
14
HINT
Source
Solution
简单的树形DP
$dp[i][j]$表示节点$i$染颜色$j$时的最小
随便转移一下...自己一开始认为就是一层1一层2但是发现好像不对,不可能这么naive,但是又实在不知道极限是多少...
PS求路过的人教我如何证明最大为3...
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 10010
int N,ans;
struct EdgeNode{int next,to;}edge[maxn<<];
int head[maxn],cnt;
void add(int u,int v)
{
cnt++;
edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;
}
void insert(int u,int v) {add(u,v); add(v,u);}
int dp[maxn][];
void DFS(int now,int fa)
{
for (int i=; i<=; i++) dp[now][i]=i;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=fa) DFS(edge[i].to,now);
for (int i=; i<=; i++)
for (int j=head[now]; j; j=edge[j].next)
if (edge[j].to!=fa)
{
int nowc=;
for (int k=; k<=; k++)
if (k!=i) nowc=nowc==?dp[edge[j].to][k]:min(nowc,dp[edge[j].to][k]);
dp[now][i]+=nowc;
}
}
int main()
{
N=read();
for (int u,v,i=; i<=N-; i++) u=read(),v=read(),insert(u,v);
DFS(,);
for (int i=; i<=; i++) ans=ans==?dp[][i]:min(ans,dp[][i]);
printf("%d\n",ans);
return ;
}
最新文章
- $event 获取对象
- DataSet转化为实体集合类
- 【WEB前端经验之谈】没有速成,只有不断积累。
- Spring IoC容器的设计——BeanFactory应用场景2
- 使用MongoDB的开源项目
- js 不可变的原始值和可变的对象引用
- 如何更好辨认House of hello恶搞包的真假
- 深入理解linux网络技术内幕读书笔记(三)--用户空间与内核的接口
- Android菜鸟的成长笔记(9)——Intent与Intent Filter(下)
- [ZZ] python 语言技巧
- 安装Visual C++ 6.0后报错:应用程序无法正常启动(0xc0000142)
- 19.Scharr滤波器
- CentOS 7 安装配置带用户认证的squid代理服务器
- nginx记录post body/payload数据
- [P4995]跳跳!(贪心)
- laravel简书(2)
- Oracle Grid 11.2.0.4 安装是出现";INS-30510: Insufficient number of ASM disks selected.";
- rook issues
- Hive将txt、csv等文本文件导入hive表
- 怎样使用DWZ?