首页 > 代码库 > POJ 1947 Rebuilding Roads
POJ 1947 Rebuilding Roads
题目大意：
根据两个点建立一条有向边，最后可形成的是一棵树，希望通过切除一些边，使一棵含有p个节点的子树被独立出来，希望切除的边数最少，输出这个边数
这个是第一次自己完完整整做出来的树形Dp题目，没有参考别人的DP思路，虽然自己很快想好了，但是总是无法合适的进行组织，做了很久，但自己做出来的
总是会比取理解别人代码来的效果好很多
用dp[u][j] 记录u号节点这棵子树中含有j个点需要砍去的最少的边数
两次dfs ， 第一次dfs查出对应节点的下方子树中一共有多少个节点，顺便记录一个节点在当前延伸出去了几条边
也就是dp[u][1] ，表示最后u代表的子树下方全部砍去只剩u这一个点
第二次dfs中自底向上不断将子树添加进来，根据dp值判断是否适合加入这个子树，如果适合加入，那么因为之前砍去的那条边要加回来，所以
砍去的边要少一
dp[u][j] = min(dp[u][j] , dp[v][k] + dp[u][j-k] - 1) k<j
这里判断dp[u][j] ， 和dp[v][k] + dp[u][j-k] - 1的大小，前一个表示没必要添加v子树，后一个表示添加了v子树效果更好
实际这里的二重循环也是相当于类似背包问题的思想
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std; 6 const int INF = 0x3f3f3f3f; 7 const int N = 205; 8 9 int dp[N][N] , sum[N] , first[N] , col[N] , root , k;10 11 struct Edge{12 int y , next;13 }e[N];14 15 void add_edge(int x , int y)16 {17 e[k].y = y , e[k].next = first[x];18 first[x] = k++;19 }20 21 void dfs1(int u)22 {23 sum[u] = 1;24 dp[u][1] = 0;25 for(int i=first[u] ; i!=-1 ; i=e[i].next){26 dp[u][1] ++;27 int v = e[i].y;28 dfs1(v);29 sum[u] += sum[v];30 }31 }32 33 void dfs2(int u , int n)34 {35 dp[u][sum[u]] = 0;36 for(int i=first[u] ; i!=-1 ; i=e[i].next){37 int v = e[i].y;38 dfs2(v , n);39 //这里j必须递减，因为运算中用到了dp[u][j-k]，如果是递增顺序，那么会提前把要使用的更新了40 for(int j=sum[u] ; j>=2 ; j--){41 for(int k=j-1 ; k>=1 ; k--){42 dp[u][j] = min(dp[u][j] , dp[v][k] + dp[u][j-k] - 1);43 }44 }45 }46 }47 48 int main()49 {50 // freopen("a.in" , "r" , stdin);51 int n , p , a , b;52 while(scanf("%d%d" , &n , &p) == 2)53 {54 memset(first , -1 , sizeof(first));55 memset(col , 0 , sizeof(col));56 k = 0;57 for(int i=1 ; i<n ; i++){58 scanf("%d%d" , &a , &b);59 add_edge(a , b);60 col[b] = 1;61 }62 for(int i = 1 ; i<=n ; i++)63 if(!col[i]) root = i;64 65 memset(dp , 0x3f , sizeof(dp));66 dfs1(root);67 dfs2(root , n);68 69 int minn = INF;70 for(int i=1 ; i<=n ; i++){71 if(i == root) minn = min(minn , dp[i][p]);72 else minn = min(minn , dp[i][p]+1);73 }74 printf("%d\n" , minn);75 }76 return 0;77 }
POJ 1947 Rebuilding Roads
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。