首页 > 代码库 > [POJ 1947]Rebuilding Roads (树形dp)
[POJ 1947]Rebuilding Roads (树形dp)
题目链接：http://poj.org/problem?id=1947
题目大意：给你一棵树，树上N个节点。问最少拆掉多少条边使得存在一个联通块，有P个节点。
树形dp，设计状态：dp[u][i]代表以u为根节点的剩下i个节点最少需要拆掉多少条边。
状态转移：dp[u][i+j] = min(dp[u][i+j],dp[u][i]+dp[v][j]-1); 其中v是u的儿子节点。
相当于在树上跑01背包，即每个儿子节点去掉剩下j个的但是要连上u-v边，或者不去掉剩下j个的。
代码：
1 import java.util.*; 2 import static java.lang.Math.*; 3 4 5 class Graph{ 6 7 ArrayList<ArrayList<Integer>> e; 8 int [][] dp; 9 int [] sum;10 boolean [] vis;11 final static int INF = 99999999;12 13 public Graph(int n){14 e = new ArrayList<ArrayList<Integer>>();15 for(int i=0;i<=n;i++){16 e.add(new ArrayList<Integer>());17 } 18 dp = new int[n+1][n+1];19 for(int i=0;i<n+1;i++){20 Arrays.fill(dp[i],INF);21 }22 sum = new int[n+1];23 vis = new boolean[n+1];24 }25 26 public void add_edge(int from,int to){27 ArrayList<Integer> t = e.get(from);28 t.add(to);29 }30 31 public void dfs(int u){32 if( vis[u] ) return;33 vis[u] = true;34 int tot = 0;35 sum[u] = 1;36 ArrayList<Integer> t = e.get(u);37 38 for(int v:t){39 if( !vis[v] ){40 tot++;41 dfs(v); 42 sum[u] += sum[v];43 } 44 }45 46 if( tot==0 ) {47 dp[u][1] = 0;48 return;49 }50 51 dp[u][1] = tot;52 for(int v:t){53 for(int i=sum[u];i>=1;i--){54 for(int j=1;j<=sum[v];j++){55 if( i+j <= sum[u] )56 dp[u][i+j] = min(dp[u][i+j],dp[u][i]+dp[v][j]-1);57 }58 }59 }60 }61 62 public int get_ans(){63 int ans = dp[1][Main.P];64 for(int i=2;i<=Main.N;i++){65 ans = min(ans,dp[i][Main.P]+1);66 }67 return ans;68 }69 70 }71 72 73 public class Main{74 static int N,P;75 static Scanner sc = new Scanner(System.in);76 public static void main(String[] args){77 while( sc.hasNext() ){78 N = sc.nextInt();79 P = sc.nextInt();80 81 Graph G = new Graph(N);82 83 for(int i=1;i<N;i++){84 int a = sc.nextInt();85 int b = sc.nextInt();86 G.add_edge(a, b); 87 }88 89 G.dfs(1);90 91 //System.out.println(G.dp[1][P]);92 int ans = G.get_ans();93 System.out.println(ans);94 }95 }96 }
[POJ 1947]Rebuilding Roads (树形dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。