本文共 1496 字，大约阅读时间需要 4 分钟。

题目连接：

题目大意：

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

题目分析：

• 定义dp[u]为以u为根的子树中要使根都可达，需要调换方向的边的条数。
• 定义dir[v]记录点v到父亲节点的边的方向。
• 然后就是将每个点提成根的操作了。
• dp[u]换成新的定义，以u为根的到达整棵树需要调整的边的条数。
• dp[u] = dp[p] + dir[u]?1:-1
• 详情见代码，这道题在D题当中算相当水的了。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAX 200007using namespace std;int n,s,t;vector
        
          e[MAX];vector
         
           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
          
            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 (""); }}
          
         
        
       
      
     
    
   

转载地址：http://iqvjn.baihongyu.com/