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