Codeforces 219D Choosing Capital for Treeland：Tree dp

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

题意：

　　给你一棵树，n个节点。

　　树上的边都是有向边，并且不一定是从父亲指向儿子的。

　　你可以任意翻转一些边的方向。

　　现在让你找一个节点，使得从这个节点出发能够到达其他所有节点，并保证翻转边的数量最小。

　　问你最少翻转多少条边，并输出所有满足此条件的节点编号。

题解：

　　本题要解两个dp: dp1 & dp2

　　首先考虑dp1：

　　　　表示状态：

　　　　　　dp1[i]表示使节点i能够到达i的子树中的所有节点，翻转边的最小数量。

　　　　如何转移：

　　　　　　dp1[i] = ∑ (dp1[son] + 边<i,son>由i指向son ? 0 : 1)

　　　　　　dfs一遍即可。

　　然后求dp2：

　　　　表示状态：

　　　　　　dp2[i]表示使节点i能够到达这棵树的所有节点，翻转边的最小数量。

　　　　如何转移：

　　　　　　dp2[i] = dp2[par] + 边<par,i>是否由par指向i ? 1 : -1

　　　　　　如果边<par,i>由par指向i，那么在dp2[par]中这条边是不会被翻转的，所以此时应该将它翻转，代价+1。

　　　　　　如果边<par,i>由i指向par，那么在dp2[par]中这条边已经被翻转了一次，然而在dp2[i]中是不需要翻转的，所以将dp2[par]中多余的那次翻转减掉就好。

　　　　边界条件：

　　　　　　dp2[1] = dp1[1]

　　　　　　（默认根节点为1）

　　所以最终答案为dp2[i]中的最小值，然后将所有dp2[i]等于ans的节点输出就好啦。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #define MAX_N 200005

 #define INF 1000000000

 using namespace std;

 struct Edge

 {

     int dest;

     bool flag;

     Edge(int _dest,bool _flag)

     {

         dest=_dest;

         flag=_flag;

     }

     Edge(){}

 };

 int n;

 int ans=INF;

 int dp1[MAX_N];

 int dp2[MAX_N];

 vector<Edge> edge[MAX_N];

 void read()

 {

     cin>>n;

     int x,y;

     for(int i=;i<n;i++)

     {

         cin>>x>>y;

         edge[x].push_back(Edge(y,true));

         edge[y].push_back(Edge(x,false));

     }

 }

 void dfs1(int now,int p)

 {

     dp1[now]=;

     for(int i=;i<edge[now].size();i++)

     {

         Edge temp=edge[now][i];

         if(temp.dest!=p)

         {

             dfs1(temp.dest,now);

             dp1[now]+=dp1[temp.dest]+(!temp.flag);

         }

     }

 }

 void dfs2(int now,int p,bool d)

 {

     if(now==) dp2[now]=dp1[now];

     else dp2[now]=dp2[p]+(d?:-);

     ans=min(ans,dp2[now]);

     for(int i=;i<edge[now].size();i++)

     {

         Edge temp=edge[now][i];

         if(temp.dest!=p) dfs2(temp.dest,now,temp.flag);

     }

 }

 void work()

 {

     dfs1(,-);

     dfs2(,-,);

     cout<<ans<<endl;

     for(int i=;i<=n;i++)

     {

         if(dp2[i]==ans) cout<<i<<" ";

     }

     cout<<endl;

 }

 int main()

 {

     read();

     work();

 }

巴特西

Codeforces 219D Choosing Capital for Treeland：Tree dp

最新文章

热门文章