HDOJ1054—— 树形DP & 二分图最小点覆盖

问题链接

问题描述

给定一个树形结构，我们可以在某些节点上安插士兵，使得与这个节点相连的边被覆盖到。求最少放多少个士兵，使得整张图的所有边都被覆盖到。

Sample Input

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

Sample Output

1
2

分析

解法一 树形DP
设DP[i][0] 为节点i不安插士兵的最小数量，dp[i][1]为节点i安插士兵的最小数量
易得状态转移方程
dp[i][0] = sum(dp[v][1]) v为i的子节点
dp[i][1] = sum(min(dp[v][0],dp[v][1]))

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1500 + 10;
vector<int> mat[maxn];
int n,dp[maxn][2];

void dfs(int root,int pre)
{
  dp[root][0] = 0;
  dp[root][1] = 1;
  for(int i=0;i<mat[root].size();i++)
  {
    int v = mat[root][i];
    if(v == pre) continue;
    dfs(v,root);
    dp[root][0] += dp[v][1];
    dp[root][1] += min(dp[v][0],dp[v][1]);
  }
}

int main()
{
  int a,b,num;
  while(cin >> n)
  {
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=n;i++)
      mat[i].clear();
    for(int i=0;i<n;i++)
    {
      scanf("%d:(%d)",&a,&num);
      for(int j=0;j<num;j++)
      {
        cin >> b;
        mat[a].push_back(b);
        mat[b].push_back(a);
      }
    }
    dfs(0,-1);
    cout << min(dp[0][0],dp[0][1]) << endl;
  }
}

解法二 二分图最小点覆盖
可以将树的奇数层放在边，偶数层放在另一边，然后将相邻节点连边。问题就是求最小的节点数覆盖所有的边，即为这张二分图的最大匹配。

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn = 1500 + 10;
vector<int> boy,mat[maxn];
int n,cnt,vis[maxn],cur[maxn];

void color(int node,int c)  //上色，将节点分成两个集合
{
  if(c == 1)  boy.push_back(node);
  vis[node] = 1;
  for(int i=0;i<mat[node].size();i++)
  {
    int v = mat[node][i];
    if(vis[v])  continue;
    color(v,-1 * c);
  }
}

bool find(int node)
{
  for(int i=0;i<mat[node].size();i++)
  {
    int v = mat[node][i];
    if(!vis[v])
    {
      vis[v] = 1;
      if(cur[v] == -1 || find(cur[v]))
      {
        cur[v] = node;
        return true;
      }
    }
  }
  return false;
}

int main()
{
  int a,b,num;
  while(cin >> n)
  {
    memset(cur,-1,sizeof(cur));
    boy.clear();
    for(int i=0;i<=n;i++) mat[i].clear();
    for(int i=0;i<n;i++)
    {
      scanf("%d:(%d)",&a,&num);
      while(num--)
      {
        cin >> b;
        mat[a].push_back(b);
        mat[b].push_back(a);
      }
    }
    memset(vis,0,sizeof(vis));
    color(0,1);
    cnt = 0;
    for(int i=0;i<boy.size();i++)
    {
      memset(vis,0,sizeof(vis));
      if(find(boy[i]))  cnt++;
    }
    cout << cnt << endl;
  }
}