首页 > 专题系列 > Java解POJ > POJ 1947 Rebuilding Roads [解题报告] Java
2013
11-10

POJ 1947 Rebuilding Roads [解题报告] Java

Rebuilding Roads

问题描述 :

The cows have reconstructed Farmer John’s farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.

Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.

输入:

* Line 1: Two integers, N and P

* Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J’s parent in the tree of roads.

输出:

A single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated.

样例输入:

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11

样例输出:

2

温馨提示:

[A subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed.]

解题代码:

import java.util.ArrayList;  
    import java.util.List;  
    import java.util.Scanner;  
      
    public class Main{  
      
        public static final int MAX = 152;  
        static List< Integer> v[];  
        static int dp[][];  
        static int p;  
        static int root;  
          
        public static void main(String[] args) {  
              
            Scanner scan = new Scanner(System.in);  
              
            int n = scan.nextInt();  
            p = scan.nextInt();  
              
            boolean s[] = new boolean[n+1];  
            v = new ArrayList[n+1];  
            java.util.Arrays.fill(s, true);  
            dp = new int[n+1][p+1];  
              
            for(int i=0;i<=n;i++)  
                java.util.Arrays.fill(dp[i], MAX);  
              
            for(int i=1;i<=n;i++)  
                v[i] = new ArrayList< Integer>();  
              
            for(int i=1;i< n;i++){  
                int u = scan.nextInt();  
                int t = scan.nextInt();  
                v[u].add(t);  
                s[t] = false;  
            }  
              
            for(int i=1;i<=n;i++){  
                if(s[i]){  
                    root = i;  
                    dfs(root);  
                    break;  
                }  
            }  
              
            int ans = MAX;  
            for(int i=1;i<=n;i++)  
                ans = Math.min(ans,dp[i][p]);  
              
            System.out.println(ans);  
      
        }  
      
        public static void dfs(int u) {  
              
            for(int i=0;i< v[u].size();i++){  
                  
                dfs(v[u].get(i));  
                  
            }  
              
            if(u == root)  
                dp[u][1] = v[u].size();  
            else  
                dp[u][1] = v[u].size()+1;  
              
            for(int i=0;i< v[u].size();i++){  
              for(int j=p-1;j>=1;j--){  
                 if(dp[u][j]< MAX){  
                    for(int k=1;k+j<=p;k++){  
                        if(dp[u][k]< MAX){  
      dp[u][j+k] = Math.min(dp[u][j+k], dp[u][j]+dp[v[u].get(i)][k]-2);//每次加一个子树 更新d[u][2..P]  
                         }  
                      }  
                  }  
                }  
            }  
              
        }  
      
    }

  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. [email protected]