树形dp裸题,不过输入是真的恶心,要字符串读入考虑数字大于等于10的情况

dp[i][j]表示i的子树在j状态的最小的边集覆盖,j为0表示不选当前结点,1表示选

转移方程(u->x是u的所有子节点)dp[u][0]+=dp[x][1],dp[u][1]+=min(dp[x][0],dp[x][1]),dp[u][1]+=1(要选自己)

#include<cstdio>
#include<iostream>
#include<cstring>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std;
using namespace __gnu_cxx; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; struct edge{
int to,Next;
}e[N<<];
int dp[N][];
int head[N],cnt;
void add(int u,int v)
{
e[cnt].to=v;
e[cnt].Next=head[u];
head[u]=cnt++;
}
void dfs(int u,int f)
{
dp[u][]=;
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f)continue;
dfs(x,u);
dp[u][]+=dp[x][];
dp[u][]+=min(dp[x][],dp[x][]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n;
while(cin>>n)
{
memset(head,-,sizeof head);
cnt=;
for(int i=; i<n; i++)
{
string s;
cin>>s;
int a=,id=;
while(id+<s.size()&&s[id+]!=':')id++;
// cout<<id<<endl;
for(int i=;i<=id;i++)a=a*+(int)(s[i]-'');
// cout<<a<<endl;
int k=,id1=id+;
while(id1+<s.size()&&s[id1+]!=')')id1++;
for(int i=id+;i<=id1;i++)k=k*+(int)(s[i]-'');
// cout<<k<<endl;
while(k--)
{
int b;
cin>>b;
add(a,b);
add(b,a);
}
}
memset(dp,,sizeof dp);
dfs(,-);
cout<<min(dp[][],dp[][])<<endl;
}
return ;
}
/************
11
0:(10) 1 2 3 4 5 6 7 8 9 10
1:(0)
2:(0)
3:(0)
4:(0)
5:(0)
6:(0)
7:(0)
8:(0)
9:(0)
10:(0)
************/

最新文章

  1. hihoCoder太阁最新面经算法竞赛15
  2. 我的iOS之路2
  3. java io读书笔记(6) Writing Arrays of Bytes
  4. vml 在IE8 不显示的问题, Group不能用等问题.
  5. [转]Linux文件和目录操作命令
  6. 无废话网页重构系列——(6)HTML主干结构:站点(site)、页面(page)
  7. 压力测试工具siege的用法
  8. CodeIgniter 框架---学习笔记
  9. comet ajax轮询
  10. Hex文件
  11. SSH服务端配置、优化加速、安全防护
  12. 深入理解java的static关键字
  13. centos6.9设置桥接网络模式方法
  14. Delphi XE5 for Android (九)
  15. 第三节 java 数组
  16. 蓝牙inquiry流程之命令下发
  17. Linux下的sqlserver简单试用
  18. css 中 stick footer 布局实现
  19. cocos2d-x3.0 macOS下配置Android开发环境以及使用cocos2d-console来新建执行project
  20. JavaBean的任务就是: “Write once, run anywhere, reuse everywhere” Enterprise JavaBeans

热门文章

  1. standard pbr(二)
  2. django实现密码加密的注册(数据对象插入)-结合forms表单实现表单验证
  3. python的语法规范及for和while
  4. MySql存储过程、函数
  5. 通过Python操作hbase api
  6. 通过profile优化SQL语句
  7. PL/SQL不能格式化SQL:--PL/SQL Beautifier could not parse text
  8. formatblock 块及
  9. 自定义Cell需要注意的问题
  10. EGLImage与纹理