codeforces 219D

题目大意：

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

题目分析：

定义dp[u]为以u为根的子树中要使根都可达，需要调换方向的边的条数。

定义dir[v]记录点v到父亲节点的边的方向。

然后就是将每个点提成根的操作了。

dp[u]换成新的定义，以u为根的到达整棵树需要调整的边的条数。

dp[u] = dp[p] + dir[u]?1:-1

详情见代码，这道题在D题当中算相当水的了。

AC代码： #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> #define MAX 200007 using namespace std; int n,s,t; vector<int> e[MAX]; vector<int> f[MAX]; int dp[MAX],dir[MAX]; void add ( int u , int v ) { e[u].push_back ( v ); f[u].push_back ( 0 ); e[v].push_back ( u ); f[v].push_back ( 1 ); } void dfs ( int u , int p ) { dp[u] = 0; for ( int i = 0 ; i < e[u].size() ; i++ ) { int v = e[u][i]; if ( v == p ) continue; dir[v] = f[u][i]; dfs ( v , u ); dp[u] += dp[v] + dir[v]; } } void solve ( int u , int p ) { for ( int i = 0 ; i < e[u].size() ; i++ ) { int v = e[u][i]; if ( v == p ) continue; dp[v] = dp[u] + (dir[v]?-1:1); solve ( v , u ); } } int main ( ) { while ( ~scanf ( "%d" , &n )) { for ( int i = 0 ; i < MAX ; i++ ) { e[i].clear(); f[i].clear(); } for ( int i = 1 ; i < n ; i++ ) { scanf ( "%d%d" , &s , &t ); add ( s , t ); } dfs ( 1 , -1 ); solve ( 1 , -1 ); int ans = 1<<29; for ( int i = 1 ; i <= n ; i++ ) ans = min ( ans , dp[i] ); printf ( "%d\n" , ans ); vector<int> pp; for ( int i = 1 ; i <= n ; i++ ) if ( dp[i] == ans ) pp.push_back ( i ); sort ( pp.begin() , pp.end()); for ( int i = 0 ; i < pp.size(); i++ ) printf ( "%d " , pp[i] ); puts (""); } }