Massive Algorithms: POJ 1947 -- Rebuilding Roads

POJ 1947 -- Rebuilding Roads

1947 -- 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.

Input

* 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.

Output

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.

Sample Input

4 11

Sample Output

Hint

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

http://www.gonglin91.com/poj-1947-rebuilding-roads/

由于我们不知道最后得到的是哪个子树，所有可以全部求出来，最后枚举每个点，以该点作为根的子树下有p个节点的切割次数是多少
定义:dp[u][m]:表示以u为根的子树下有m个节点的最小切割次数，注意这里，u和它的父亲fa的连边是没有切断的，但是我们并不考虑它的fa分支，只看u这个子树，所以最后要使的u这个子树完全独立出来，还要切割多一次，切断u和fa的连线
最终的答案是
ans = dp[1][p];以1为根的子树下有p个节点的最少切割次数，由于1没有fa，所以不用加1
ans = min{ dp[u][p] } + 1 ; 以其他点为根的子树下有p个节点的最少切割次数，但是其他节点u都有fa，所以还要切掉u和fa的边

dp的转移：我们先来考虑这个问题。u为根的子树有m个节点，u有儿子v1，v2，v3,…….假设v1子树有k1个节点，v2子树有k2的节点，v3子树有k3个节点………….这其实就是一个组合起来的结果
dp[u][m] = dp[v1][k1] + dp[v2][k2] + dp[v3][k3] + dp[v4][k4]………………….
但每个子树下面保留多少个节点，是不确定的，可以1个，0个，多个。这其实就转化为了背包
总容量为m，每个子树下应该选进去多少个点ki，使得不超过容量m，价值最小

转移方程为
dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] – 1);
有时候写dp[u][j]会不好理解，实际上是dp[u][c][j]的，只不过和背包一样，进行了空间的优化，降维
dp[u][c][j]表示以u为根的子树，在考虑第前c个儿子子树后，包含了j个节点的最少切割次数，这和dp[u][j]是一样的

dp[u][1] = son; 以u为根的子树只保留一个节点u，那么说明其儿子都切断了，有多少个儿子子树只需要切多少刀，因而切son次

关于转移方程 dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] – 1);
dp[u][j-k] + dp[v][k] – 1 , dp[u][j-k]表示前c个儿子一共贡献了j-k个节点给u这个子树，dp[v][k]表示第c+1个儿子贡献了k个节点给u，为何要减1，因为对于u而言，相当于v子树拼接到u上次，要抵消掉之前切去的那条u—v的边.

int dp[N][N];
 
void dfs(int u,int fa){
 int son = 0;
 for(int i = 0; i < e[u].size(); i++){
  int v = e[u][i];
  if(v == fa) continue;
  dfs(v,u);
  son++;
 }
 dp[u][1] = son;
 for(int i = 0; i < e[u].size(); i++){
  int v = e[u][i];
  if(v == fa) continue;
  for(int j = p; j >= 2; j--)
   for(int k = 1; k < j; k++)
    if(dp[u][j-k] != INF && dp[v][k] != INF){
     dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] - 1);
    }
 }
}
 
int main(){
 while(scanf("%d%d",&n,&p)!=EOF){
  for(int i = 1; i <= n; i++)
   e[i].clear();
  for(int i = 1; i < n; i++){
   int u,v;
   scanf("%d%d",&u,&v);
   e[u].pb(v); e[v].pb(u);
  }
  cl(dp,0x3f);
  dfs(1,-1);
  int ans = INF;
  for(int i = 1; i <= n; i++){
   if(i == 1) ans = min(ans,dp[i][p]);
   else ans = min(ans,dp[i][p]+1);
  }
  printf("%d\n",ans);
 }
 return 0;
}

http://blog.csdn.net/tc_to_top/article/details/44134065

一颗含有n个结点的树，求减去最少的边使得该树只含有p个结点

题目分析：典型的树形dp，在树上进行动态规划，设dp[s][i]表示以s为根的子树含有i个结点需要删去的边数，则得到转移方程：

对于i的子树k:

1.不加子树k，dp[s][i] = dp[s][i] + 1 （不加子树k，相当于删去一条边）

2.加子树k，dp[s][i] = min(dp[s][j] ＋ dp[k][i - j]) (1<= j <= i) (以s为根的树的结点数加上其子树的结点数等于i)

最后答案就是在dp[i][m]中取小，要注意的一点是，如果i不是根，值还需要＋1，因为要脱离原来的根，还要去掉一条边

这里需要注意，dp过程是自下而上的，也就是从叶子到根，而不是从根到叶子

struct Edge
{
int to, next;
}e[MAX * MAX / 2];
int n, m;
int head[MAX], cnt, root;
int fa[MAX], dp[MAX][MAX];
void Add(int x, int y) //加边
{
e[cnt].to = y;
e[cnt].next = head[x];
head[x] = cnt++;
}
void DFS(int u)
{
for(int i = 0; i <= m; i++) //初始化为无穷大
dp[u][i] = INF;
dp[u][1] = 0; //根结点本就一个点，不需要减边
for(int i = head[u]; i != -1; i = e[i].next) //同层
{
int v = e[i].to; //u的子树
DFS(v);
for(int j = m; j >= 1; j--)
{
for(int k = 0; k < j; k++)
{
if(k) //不加子树k
dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k]);
else //加上子树k
dp[u][j] = dp[u][j] + 1;
}
}
}
}
int main()
{
scanf("%d %d", &n, &m);
cnt = 0;
memset(fa, -1, sizeof(fa));
memset(head, -1, sizeof(head));
for(int i = 1; i < n; i++)
{
int x, y;
scanf("%d %d", &x, &y);
Add(x, y);
fa[y] = x;
}
for(root = 1; fa[root] != -1; root = fa[root]);
DFS(root);
int ans = dp[root][m];
for(int i = 1; i <= n; i++) //除了根节点，其他节点要想成为独立的根，必先与父节点断绝关系，所以要先加1
ans = min(ans, dp[i][m] + 1);
printf("%d\n",ans);
}

http://blog.csdn.net/sdjzping/article/details/18563289

这是一道树形DP，对于第k条边来说要么删除要么不删除

dp[i][j]表示以i为根的树有j个结点的最小代价（最少删除的边数），

dp[u][j]=max(dp[u][j]+1,dp[u][j-k]+dp[v][k])

要是删除第k条边那么dp[u][j]=dp[u][j]+1,不删除第K条边就等于dp[u][j-k]+dp[v][k]

http://blog.csdn.net/wujysh/article/details/38356847

树形DP，dp[i][j]表示以i节点为根，恰有j个节点时，需要去除几条边。

dp[father][i+j] = min(dp[father][i+j], dp[father][i] + dp[child[father][k]][j] - 2);

dp[father][1] = child[father].size() + 1;

dp[root][1] = child[root].size();

void dfs(int x) {
for (int i = 0; i < child[x].size(); i++) {
dfs(child[x][i]);
}
for (int s = 0; s < child[x].size(); s++) {
for (int i = p; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
dp[x][i] = min(dp[x][i-j] + dp[child[x][s]][j] - 2, dp[x][i]);
}
}
}
}
void work() {
for (int i = 0; i <= n; i++) {
dp[i][1] = child[i].size() + 1;
}
dp[root][1] = child[root].size();
dfs(root);
for (int i = 1; i <= n; i++) {
ans = min(ans, dp[i][p]);
}
}

http://www.cnblogs.com/CKboss/p/3350821.html
int dp[200][200],sum[200],N,P;
vector<int> g[200];
bool vis[200];

void Tree_DP(int s)
{
    if(vis[s]) return;
    int tot = 0;
    vis[s]=true;sum[s]=1;
    for(int i=0;i<g[s].size();i++)
    {
        int v=g[s];
        if(vis[v]) continue;
        Tree_DP(v);
        sum[s]+=sum[v];
        tot++;
    }
    dp[s][1]=tot;
    for(int i=0;i<g[s].size();i++)
    {
        int v=g[s];
        for(int j=sum[s];j>=2;j--)
        {
            for(int k=1;k<j;k++)
            {
                if(dp[s][k]!=INF&&dp[v][j-k]!=INF)
                {
                    dp[s][j]=min(dp[s][j],dp[s][k]+dp[v][j-k]-1);
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d%d",&N,&P)!=EOF)
    {
        for(int i=0;i<N+10;i++)
            g.clear();
        for(int i=0;i<N-1;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g.push_back(a);
        }
        memset(dp,63,sizeof(dp));
        memset(vis,false,sizeof(vis));
        memset(sum,0,sizeof(sum));
        Tree_DP(1);
        int ans=INF;
        for(int i=1;i<=N;i++)
        {
            if(i==1)
                ans=min(ans,dp[P]);
            else ans=min(dp[P]+1,ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}
http://www.java3z.com/cwbwebhome/article/article17/acm894.html
Read full article from 1947 -- Rebuilding Roads

POJ 1947 -- Rebuilding Roads

Labels

Popular Posts