Codeforces 219D Choosing Capital for Treeland：Tree dp

2021-04-21 23:26

阅读：473

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

题意：

　　给你一棵树，n个节点。

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

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

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

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

题解：

　　本题要解两个dp: dp1 & dp2

　　首先考虑dp1：

　　　　表示状态：

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

　　　　如何转移：

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

　　　　　　dfs一遍即可。

　　然后求dp2：

　　　　表示状态：

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

　　　　如何转移：

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

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

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

　　　　边界条件：

　　　　　　dp2[1] = dp1[1]

　　　　　　（默认根节点为1）

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

AC Code:

 1 #include  2 #include  3 #include string.h>
 4 #include  5 #define MAX_N 200005
 6 #define INF 1000000000
 7 
 8 using namespace std;
 9 
10 struct Edge
11 {
12     int dest;
13     bool flag;
14     Edge(int _dest,bool _flag)
15     {
16         dest=_dest;
17         flag=_flag;
18     }
19     Edge(){}
20 };
21 
22 int n;
23 int ans=INF;
24 int dp1[MAX_N];
25 int dp2[MAX_N];
26 vector edge[MAX_N];
27 
28 void read()
29 {
30     cin>>n;
31     int x,y;
32     for(int i=1;i)
33     {
34         cin>>x>>y;
35         edge[x].push_back(Edge(y,true));
36         edge[y].push_back(Edge(x,false));
37     }
38 }
39 
40 void dfs1(int now,int p)
41 {
42     dp1[now]=0;
43     for(int i=0;i)
44     {
45         Edge temp=edge[now][i];
46         if(temp.dest!=p)
47         {
48             dfs1(temp.dest,now);
49             dp1[now]+=dp1[temp.dest]+(!temp.flag);
50         }
51     }
52 }
53 
54 void dfs2(int now,int p,bool d)
55 {
56     if(now==1) dp2[now]=dp1[now];
57     else dp2[now]=dp2[p]+(d?1:-1);
58     ans=min(ans,dp2[now]);
59     for(int i=0;i)
60     {
61         Edge temp=edge[now][i];
62         if(temp.dest!=p) dfs2(temp.dest,now,temp.flag);
63     }
64 }
65 
66 void work()
67 {
68     dfs1(1,-1);
69     dfs2(1,-1,233);
70     coutendl;
71     for(int i=1;i)
72     {
73         if(dp2[i]==ans) cout" ";
74     }
75     coutendl;
76 }
77 
78 int main()
79 {
80     read();
81     work();
82 }

上一篇：cmake3.8X64编译opencv3.2出现opencv_ffmpeg、opencv_ffmpeg_64、ippicv_windows_20151201.zip无法下载问题解决方案

下一篇：windows10图形化连接CentOS7

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Codeforces 219D Choosing Capital for Treeland：Tree dp
文章链接：http://soscw.com/index.php/essay/77809.html

亲，登录后才可以留言！

Codeforces 219D Choosing Capital for Treeland：Tree dp

评论

热门文章

推荐文章

最新文章

置顶文章