P2016 战略游戏——树形DP大水题
2024-08-22 23:44:17
P2016 战略游戏
树形DP 入门题吧(现在怎么是蓝色标签搞不懂);
注意是看见每一条边而不是每一个点(因为这里错了好几次);
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int pre[maxn],last[maxn],other[maxn],l; void add(int x,int y)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
} int n;
int f[maxn][]; void dfs(int x,int fa)
{
f[x][]=;f[x][]=;
for(int p=last[x];p;p=pre[p])
{
int v=other[p];
if(v==fa) continue;
dfs(v,x);
f[x][]+=min(f[v][],f[v][]);
f[x][]+=f[v][];
}
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x,k,y;
scanf("%d%d",&x,&k);
x++;
for(int j=;j<=k;j++)
{
scanf("%d",&y);
y++;
add(x,y);
add(y,x);
}
}
dfs(,);
printf("%d",min(f[][],f[][]));
return ;
}
最新文章
- SRM 146 DIV1 600
- 《ODAY安全:软件漏洞分析技术》学习心得-----shellcode的一点小小的思考
- Could not find a storyboard named &#39;Main&#39; in bundle NSBundle
- 【M26】限制某个class所能产生的对象数量
- Java基础知识强化96:Calendar类之获取任意年份的2月有多少天的案例
- 微信公众号平台接口开发:基础支持,获取微信服务器IP地址
- HDU1305 Immediate Decodability(水题字典树)
- windows创建域共享文件
- Linux 的文件权限和目录配置
- git pull request 流程
- LeetCode--042--接雨水(java版)
- Hadoop的本地库(Native Libraries)介绍
- 编写自己的SpringBoot-starter
- Android——继续深造——从安装Android Studio 2.0开始(详)
- MySQL学习笔记:循环生成5万行id连续的数据
- Importing/Indexing database (MySQL or SQL Server) in Solr using Data Import Handler--转载
- WebStorm的主题与设置
- Mysql5.7 用户与授权
- 字符串(PHP学习)
- 转载:小白使用eclipse提交到GitHub (详细步骤)