首页 > 代码库 > codeforces 219D 树形dp
codeforces 219D 树形dp
题目大意：
根据n个城市，设置n-1条有向边，希望设定一个中心城市，能通过修改一些道路的方向到达任何一座城市，希望修改的道路数量最少
输出这个最少的道路数量，并且把所有符合的可作为中心的城市编号一个个输出来
开始也实在想不出，根据树形dp，首先要确定一棵树，可是这里的边乱七八糟的，没法确定根
后来看了别人的思路，原来还是自己太死脑筋了，根本不需要确定根，可以把任意一个城市作为根来解决题目，这里假定1为根
把所有的有向边看作无向边，但要记录那条边是真实存在的，哪条是自己加的
用dp[i]表示 i 点到达其对应的子树中的所有点需要修改的边的数量
用一次dfs得到dp[i]
然后网上的大牛们都说2次dfs，后一次因为没写清楚，自己也不想看代码，就自己想了，可就是没办法写出dfs，最后发现直接就可以循环做。。。而且更好理解
做法：
len[i]记录 i 到 root 这里定义root为 1 长度，也就是i 到 1 之间有多少条边
change[i] 表示这 len[i]条边中有多少条改变了
这两个值可以在第一次dfs中实现
然后对于每一个点 i 来说，其实为了让 i 能够到达任何一点，只要改动 i 到 1 这len[i]条边即可，画个图很容易发现
1作为树根，i 到 1 的过程经过的都是一棵棵子树的根，能到达这些子树的根，必能到达子树中的任何一点，所以希望能够到达 1 即可
用rec[i]记录以 i 为中心城市需要改动的边
rec[i] = dp[1] - change[i] + (len[i] - change[i]) //减第一个change[i]是把原来改过的边改回来，然后+后面的是因为为了 i 到1，需要将那些
方向正常的 len[i] - change[i]倒转
最后通过rec[i]得到答案即可= =
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int N = 200005; 6 7 int first[N] , k , len[N] , change[N] , dp[N] , rec[N]; 8 9 struct Edge{10 int y , next;11 bool flag;12 }e[N<<1];13 14 void add_edge(int x , int y , bool flag)15 {16 e[k].y = y , e[k].next = first[x] , e[k].flag = flag;17 first[x] = k++;18 }19 20 void dfs(int u , int fa)21 {22 for(int i = first[u] ; i!=-1 ; i=e[i].next){23 int v = e[i].y;24 if(v == fa) continue;25 len[v] = len[u]+1;26 change[v] = change[u];27 if(!e[i].flag) change[v]++;28 dfs(v , u);29 if(!e[i].flag){30 dp[u] += dp[v]+1;31 }32 else{33 dp[u] += dp[v];34 }35 }36 }37 38 int main()39 {40 // freopen("a.in" , "r" , stdin);41 int n , a , b;42 while(scanf("%d" , &n) == 1)43 {44 memset(first , -1 , sizeof(first));45 k = 0;46 for(int i=1 ; i<n ; i++){47 scanf("%d%d" , &a , &b);48 add_edge(a , b , true);49 add_edge(b , a , false);50 }51 memset(dp , 0 , sizeof(dp));52 len[1] = 0 , change[1] = 0;53 dfs(1 , -1);54 55 int minn = 200000000;56 57 for(int i=1 ; i<=n ; i++){58 rec[i] = dp[1] + len[i] - 2*change[i];59 // cout<<"i: "<<i<<" "<<len[i]<<" "<<change[i]<<" "<<rec[i]<<endl;60 minn = min(minn , rec[i]);61 }62 printf("%d\n" , minn);63 int num = 0;64 for(int i=1 ; i<=n ; i++){65 if(minn == rec[i]){66 if(num == 0) printf("%d" , i);67 else printf(" %d" , i);68 num ++;69 }70 }71 printf("\n");72 }73 return 0;74 }
codeforces 219D 树形dp