题目链接:https://vjudge.net/problem/UVALive-2038

题意:我看了原题,lrj的书上题意写错了,应该是最少点覆盖,当然可以用最大匹配去做,由于是树形的;

可以树形DP;

d[u][0] : u 结点 不放;

d[u][1] : u 结点放;

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;
int n;
vector<int> G[maxn]; int d[maxn][];
int p[maxn]; int dfs(int u,int fa) {
int d = G[u].size();
for(int i=;i<d;i++)
{
int v = G[u][i];
if(v!=fa)
dfs(v,p[v]=u);
}
} int dp(int cur,int f,int pa) {
if(d[cur][f]>)
return d[cur][f];
if(f==) {
d[cur][f] = ;
for(int i=;i<G[cur].size();i++) {
int v = G[cur][i];
if(v!=pa)
d[cur][f] +=min(dp(v,,cur),dp(v,,cur));
}
}
else {
for(int i=;i<G[cur].size();i++) {
int v = G[cur][i];
if(v!=pa)
d[cur][f] +=dp(v,,cur);
}
}
return d[cur][f];
} int main()
{
while(scanf("%d",&n)!=EOF) { memset(d,,sizeof(d));
for(int i=;i<n;i++)
G[i].clear();
int u,v,num;
for(int i=;i<n;i++) {
scanf("%d:(%d)",&u,&num);
for(int j=;j<num;j++) {
scanf("%d",&v);
G[u].push_back(v);
G[v].push_back(u);
}
} p[] = -;
dfs(,-);
printf("%d\n",min(dp(,,-),dp(,,-))); }
return ;
}

最新文章

  1. Bubble Sort (5775)
  2. bootstrap 20161012
  3. [转]svn 清理失败 (cleanup 失败) 的解决方法
  4. 支持Cookie并开放了一些特殊设置项的HttpWebClient
  5. 数据库操作事务IsolationLevel 枚举
  6. 彻底删除java*
  7. 如何自适应网页的协议(http/https/……)
  8. Android TextView换行问题
  9. 深入了解一下PYTHON中关于SOCKETSERVER的模块-B
  10. iOS获取文件路径
  11. http 请求安全
  12. delphi 利用HTTP的POST方法做个在线翻译的小工具 good
  13. Knockout js 绑定 radio 时,当绑定整形的时候,绑定不生效
  14. 锤子便签的 monkeyrunner 测试脚本(转)
  15. Swift3.0 中 Strings/Characters 闲聊
  16. js获取当前时间并实时刷新
  17. *&amp;p理解
  18. ajax用户是否存在
  19. wtf_1234
  20. PHP错误日志记录:display_errors与log_errors的区别

热门文章

  1. quartz使用(整合spring)
  2. Nginx实践:(2) Nginx语法之localtion
  3. 微信小程序转百度小程序修改
  4. I/O流复制文本
  5. jQuery easyUI 的combogrid进行模糊匹配
  6. Apache-Maven 的安装及配置
  7. Java流和文件
  8. 关于EF执行返回表的存储过程
  9. mysql应用学习-解决数据乱码
  10. BindingResult参数验证的跨层次迭代验证