Codeforces 219D Choosing Capital for Treeland:Tree dp
2021-04-21 23:26
题目链接: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] + 边
如果边
如果边
边界条件:
dp2[1] = dp1[1]
(默认根节点为1)
所以最终答案为dp2[i]中的最小值,然后将所有dp2[i]等于ans的节点输出就好啦。
AC Code:
1 #include2 #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 }
文章标题:Codeforces 219D Choosing Capital for Treeland:Tree dp
文章链接:http://soscw.com/essay/77809.html