http://codeforces.com/problemset/problem/219/D

题目大意:

给出一棵树,但是它的边是有向边,选择一个城市,问最少调整多少条边的方向能使一个选中城市可以到达所有的点,输出最小的调整的边数,和对应的点。

思路:先预处理一个点为根的代价,然后去dfs移动,总复杂度是O(n)

 #include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
int tot,go[],next[],first[],id[];
int son[],f[],v[],n;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y,int Id){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
id[tot]=Id;
}
void add(int x,int y){
insert(x,y,);insert(y,x,-);
}
void dfs(int x,int fa){
son[x]=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
if (id[i]==-) v[pur]=;
dfs(pur,x);
son[x]+=son[pur]+v[pur];
}
}
void dp(int x,int fa){
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
if (id[i]==) f[pur]=f[x]+;
else f[pur]=f[x]-;
dp(pur,x);
}
}
int main(){
n=read();
for (int i=;i<n;i++){
int x=read(),y=read();
add(x,y);
}
dfs(,);
f[]=son[];
dp(,);
int ans=n;
for (int i=;i<=n;i++) ans=std::min(ans,f[i]);
printf("%d\n",ans);
for (int i=;i<=n;i++) if (ans==f[i])
printf("%d ",i);
return ;
}

最新文章

  1. APP注释代码
  2. 【网络资料】如何优雅地使用Sublime Text3
  3. mac配置vim-go
  4. oracle中substr函数的用法
  5. linux od命令: 按不同进制显示文件
  6. German Collegiate Programming Contest 2013:E
  7. 老生常谈的Javascript作用域问题
  8. LightOJ 1338 &amp;&amp; 1387 - Setu &amp;&amp; LightOJ 1433 &amp;&amp; CodeForces 246B(水题)
  9. 【BZOJ1132】【POI2008】Tro 计算几何 叉积求面积
  10. Hadoop里的Partitioner
  11. c# propertyGrid下拉选项
  12. (数字IC)低功耗设计入门(一)
  13. [转] .NET领域驱动设计—初尝(原则、工具、过程、框架)
  14. Linux云计算 面试时最常遇到的40个问题
  15. SpringBoot14 SpringBoot整合mybatis
  16. js &amp; replaceAll &amp; Regex
  17. vim学习笔记(11):vim 去掉&lt;200b&gt;
  18. LevelDB 读取记录
  19. HDU - 5936: Difference(暴力:中途相遇法)
  20. 39、count_rpkm_fpkm_TPM

热门文章

  1. 【HDOJ】3518 Boring Counting
  2. SRM 585 DIV1
  3. (转)Android签名详解(debug和release)
  4. SQL 查询某字段id为空(不为空)
  5. Codeforces 486C Palindrome Transformation(贪心)
  6. C# WPF 建立渐隐窗口
  7. Python之基础(二)
  8. [编译原理代码][NFA转DFA并最小化DFA并使用DFA进行词法分析]
  9. Linux命令 rpm
  10. C#高级编程第1章-.NET体系结构