题目链接:http://codeforces.com/contest/219/problem/D

题目大意:

  给定一个n个节点的数和连接n个节点的n - 1条有向边,现在要选定一个节点作为起始节点,从这个点出发需要能走到其余每个节点,途中必然要调整有向边的方向,请求出当选定哪些节点作为初始节点时,所要调整的有向边最少,输出最小调整的边数和这些节点。

分析:

  Hint:城市结构是树型结构。

代码如下:

 #include <bits/stdc++.h>
using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define LOWBIT(x) ((x)&(-x)) #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a)) #define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} typedef long long LL;
typedef unsigned long long uLL;
const int inf = 1e9 + ;
const LL mod = 1e9 + ;
const int maxN = 2e5 + ; struct Node{
vector< pii > next;
}; int n, ans;
// dp[i]表示以i号城市为首都所要反转的道路数
int dp[maxN];
int vis[maxN];
Node nodes[maxN];
queue< int > Q; // 求dp[x]
inline int dfs(int x) {
if(nodes[x].next.empty()) return ; int ret = ;
foreach(i, nodes[x].next) {
int y = i->fi, z = i->se;
if(vis[y]) continue;
vis[x] = ;
if(z == -) ++ret;
ret += dfs(y);
}
return ret;
} // 如果dp[i]已知,假设j号城市与i号城市相连,由于整个城市图是树形结构,
// 因此dp[j]与dp[i]除了他们的连线有分歧,其余应该反转的道路数量都是一样的
// 因此可由已算出来的1号城市为中心,向外做BFS
inline void bfs() {
ms0(vis);
vis[] = ;
Q.push();
ans = dp[]; while(!Q.empty()) {
int tmp = Q.front();
Q.pop(); foreach(i, nodes[tmp].next) {
int y = i->fi, z = i->se;
if(vis[y]) continue;
vis[y] = ;
dp[y] = dp[tmp] + z;
ans = min(ans, dp[y]);
Q.push(y);
}
}
} int main(){
while(cin >> n) {
ms0(vis);
rep(i, n + ) nodes[i].next.clear();
rep(i, n-) {
int x, y;
cin >> x >> y;
nodes[x].next.push_back(mp(y, ));
nodes[y].next.push_back(mp(x, -));
}
dp[] = dfs(); bfs(); cout << ans << endl;
For(i, , n) if(ans == dp[i]) cout << i << " ";
cout << endl;
}
return ;
}

最新文章

  1. 【JAVA面试题系列一】面试题总汇--JAVA基础部分
  2. SpringMVC入门案例及请求流程图(关于处理器或视图解析器或处理器映射器等的初步配置)
  3. java中readLine()方法为什么有的行读不到?
  4. [Tool] SourceTree操作中遇到错误(Filename too long)的解决方案
  5. UIScrollView的delegate方法妙用之让UICollectionView滑动到某个你想要的位置
  6. MongoDB学习笔记~MongoDB实体中的值对象
  7. C# 从字符串中取出英文字母
  8. angularjs 权威指南 版本 1.2.6
  9. archlinux 内核编译笔记
  10. IOS之Core Foundation框架和Cocoa Foundation框架的区别
  11. DBA_Oracle Startup / Shutdown启动和关闭过程详解(概念)
  12. Excel导入导出帮助类
  13. 定时排程刷新微信access-token
  14. Linux软件间的依赖关系(转)
  15. NSSortDescriptor(数组排序)
  16. vue 在已有的购买列表中(数据库返回的数据)修改商品数量
  17. bootstrap手风琴折叠
  18. PHPCMS V9开发文档
  19. iOS正确解决隐藏导航栏后push和pop或dismiss和present闪黑问题
  20. python Queue在两个地方

热门文章

  1. JavaScript的工作原理:解析、抽象语法树(AST)+ 提升编译速度5个技巧
  2. 【AO笔记】有关TIN数据集的常用介绍
  3. Mysql表分区的选择与实践小结
  4. linux c ---raise 使用范例的代码
  5. 在angular 6中使用 less
  6. npm缺少css-loader,/style-compiler,stylus-loader问题,npm没有权限无法全局更新问题【已解决】
  7. [20190415]关于shared latch(共享栓锁).txt
  8. 高端内存映射之kmap持久内核映射--Linux内存管理(二十)
  9. 网络威胁实时地图(CyberThread Real-time Map)
  10. java实现简单的solr查询