注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

Codeforces Round #216 (Div. 2) Pro.C Valera and Elections  

2013-11-30 04:21:10|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://codeforces.com/contest/369/problem/C
题意:
n个节点,n-1条边组成的树,边有两种,1代表边是好的,2代表边是要修补的。选择任意一个节点k,能够把k到1之间所有的路都修好,问如何选择最少点使得所有的路都能修好。输出点个数以及点的编号,多个结果输出任意一个。
题解:
简单dfs。以节点1为根节点建立树,按照当前节点和父节点边的好坏以及每个子树中是否有坏边进行分类讨论,具体的见代码。
ps: 注意下map<pair<int,int>,int>mp;和mp[make_pair(tmp,pre)]的写法。

const int N=100010;
int n,vis[N];
vector<int>v[N];
vector<int>res;
map<pair<int,int>,int>mp;

int dfs(int tmp,int pre)
{
int s=0;
for(int i=0;i<(int)v[tmp].size();i++)
{
int t=v[tmp][i];
if(!vis[t])
{
vis[t]=1;
s+=dfs(t,tmp);
}
}

if(s == 0) //如果子树中没有坏边分类讨论
{
if(mp[make_pair(tmp,pre)] == 1) //如果当前节点和父节点连的边是好的则返回0
return 0;
else //否则返回1,且该节点作为被选择的点。
{
res.push_back(tmp);
return 1;
}
}
else //如果子树中有坏边直接返回1
return 1;
}

void solve()
{
int a,b,c;
for(int i=1;i<=n;i++)
v[i].clear();
res.clear();
mp.clear();
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
v[a].push_back(b);
v[b].push_back(a);
mp[make_pair(a,b)]=c;
mp[make_pair(b,a)]=c;
}
MEM(vis);vis[1]=1;
for(int i=0;i<(int)v[1].size();i++)
{
vis[v[1][i]]=1;
dfs(v[1][i],1);
}
printf("%d\n",res.size());
for(int i=0;i<(int)res.size();i++)
{
if(i != 0)
printf(" ");
printf("%d",res[i]);
}
printf("\n");
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
//freopen("textout.txt", "w", stdout);
#endif
while(scanf("%d",&n)!=EOF)
solve();
return 0;
}



  评论这张
 
阅读(111)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017