uva1292 树形dp
2024-10-17 09:51:23
这题说的是给了一个n个节点的一棵树,然后 你 从 这 棵 树 的 n 个 节点中 选择 尽量少的 点使得 每条边都至少有一个 士兵看守
dp[0][i]+=dp[1][j] dp[1][i]+=min(dp[0][j],dp[1][j]);
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
const int maxn = ;
int dp[][maxn];
vector<int>F[maxn];
bool use[maxn];
void inti(int n){
for(int i=; i<=n; ++i){
F[i].clear();
}
memset(use,false,sizeof(use));
memset(dp,,sizeof(dp));
for(int i=; i<n; ++i){
int d,num;
scanf("%d:(%d)",&d,&num);
for(int i=; i<num; ++i){
int a;
scanf("%d",&a);
F[a].push_back(d);
F[d].push_back(a);
}
}
}
void dfs(int now){
dp[][now]=;
dp[][now]=;
use[now]=true;
for(int i=; i<int(F[now].size()) ; ++i){
int to = F[now][i];
if(use[to]) continue;
dfs(to);
dp[][now]+= dp[][to];
dp[][now]+=min(dp[][to],dp[][to]);
}
}
int main()
{
int n;
while(scanf("%d",&n)==){
inti(n);
int ans=;
for(int i=; i<n; ++i){
if(use[i]==false){
dfs(i);
ans+=min(dp[][i],dp[][i]);
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 安装node-sass提示没有vendor目录的解决办法
- javascript原型prototype浅识
- SpringCloud Sleuth 使用
- 转载:Bootstrap之表格checkbox复选框全选
- flask_分页
- MySQL 安装 启动 基本语法概述
- git之远程标签下载(远程分支)
- 一个简单的任务执行时间监视器 StopWatch
- 十、ios 模态窗口[实例]
- zepto源码--核心方法7(管理包装集)--学习笔记
- PL/SQL注册码
- Visual Studio的MethMVVM
- codeforces #313 div1 D
- rsyslog imfile 模块说明
- javascript 冒泡和事件源 形成的事件委托
- android自己定义ViewPager之——3D效果应用
- 程序猿进化 - 在拉钩子1024对APE节讲座计划
- SQL复习四(完整性约束)
- 201521123008《Java程序设计》第1周学习总结
- Android真机安装sqlite3的方法
热门文章
- VC++第三方库配置-OpenSpirit 4.2.0 二次开发
- file.wirtelines()方法【python】
- IT教程视频
- iOS开发:iOS中图片与视频一次性多选 - v2m
- stl中的map经验
- [转]C++结构体|类 内存对齐详解
- 破谣言——iPhone砍价
- linux下远程服务器批量执行命令及SFTP上传文件 -- python实现
- iPad - 开发(Universal Applications)
- Spring 加载配置文件的方式