胡乱分析

最小覆盖集的问题就是问你最少放多少个节点的东西使得所有的节点或者边被全部的覆盖，其中规定当前节点只能覆盖相邻的节点或者边
首先这类问题分为两类一种是边全部覆盖，一种是点全部覆盖。

边全部覆盖问题

首先谈一下边全部覆盖的时候的情况
如果要边全部覆盖，那么我们可以发现一个问题，就是当前的每一个节点都包含两种情况那就是放上或者不放上
如果我们把dp[p][1]代表当前节点要放上东西把dp[p][0]代表当前节点不放东西的话,那么我们可以得出一个简单的状态转移方程
dp[p][1]+=min(dp[v][1],dp[v][0])
dp[p][0]+=dp[v][1]
其中v是儿子节点也就是说如果当前节点要放的话那么儿子节点可放可不放我们需要取一个min,如果当前节点不放的话那么儿子一定要放上一个

代码(poj 1463)

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> G[6505];
int dp[6505][6],bk[6505];
void dfs(int p)
{
  dp[p][1]=1;
  dp[p][0]=0;
  for(int i=0;i<G[p].size();i++)
  dfs(G[p][i]);
  for(int i=0;i<G[p].size();i++)
  {
    dp[p][1]+=min(dp[G[p][i]][0],dp[G[p][i]][1]);
    dp[p][0]+=dp[G[p][i]][1];
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  while(cin>>n)
  {
    for(int i=0;i<n;i++)
    G[i].clear();
    memset(dp,0,sizeof(dp));
    memset(bk,-1,sizeof(bk));
    for(int i=0;i<n;i++)
    {
      int st,m;
      char a,b,c;
      cin>>st>>a>>b>>m>>c;
      while(m--)
      {
        int ed;
        cin>>ed;
        bk[ed]=st;
        G[st].push_back(ed);
      }
    }
    int rt=0;
    while(bk[rt]!=-1)
    rt=bk[rt];
    dfs(rt);
    cout<<min(dp[rt][0],dp[rt][1])<<"\n";
  }
}

点全部覆盖问题

这个看上去好像跟边全部覆盖是一个意思的但是有不同。比如这组数据
7
1 2
1 3
2 4
2 5
3 6
6 7
这里如果是边覆盖那么是3,点覆盖那么是2
为什么会这样？
因为我们边覆盖如果要覆盖父亲节点,那么我们与所有儿子节点的边必须都得被覆盖，也就是如果父亲节点不放的话,那么儿子节点一定得放上,但是点覆盖不一样，我们的一个儿子只要放上那么这个父亲节点就已经被覆盖了所以我们得想别的办法
搞了快一晚上这个问题还是凯哥最后解决了这个问题。。。
用贪心算法也就是选择当前最好的选择
我们定义两个记录的数组bk 和 ok
bk是当前节点是不是放一个 ok是代表这个节点是不是已经遍历过了这样我们的贪心策略就是
看当前节点的父节点如果父节点没有被放上那么我们就把当前的父节点放上然后子节点和祖父节点全部都放上被遍历过的标记
这里还延伸除了另一个问题就是我们回溯的时候要把这个贪心的代码放在哪个地方？
我最初的时候想的是和dp一样直接放在dfs后面每次回溯都计算但是我得到了一个wa
凯哥给的答案是放在最后回溯也就是遍历完所有的子节点之后再回溯并且给出了一个反例
如果当前的子节点的左孩子是一个叶子节点但是右儿子不是叶子节点的话那么就会出现问题，所以要每次遍历之后回溯

代码(poj 3659)

#include <iostream>
#include <vector>
using namespace std;
vector<int> G[10005];
int bk[10005],mk[10005],f[10005],ans;
int ok[10005];
void dfs(int p,int fa)
{
  f[p]=fa;
  for(int i=0;i<G[p].size();i++)
  if(G[p][i]!=fa)
  {
    f[G[p][i]]=p;
    dfs(G[p][i],p);
  }
  if(!ok[p])
  {
    if(!bk[fa])
    {
      ans++;
      bk[fa]=1;
      ok[fa]=1;
      ok[p]=1;
      ok[f[fa]]=1;
    }
    else ok[p]=1;
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<n;i++)
  {
    int st,ed;
    cin>>st>>ed;
    G[ed].push_back(st);
    G[st].push_back(ed);
  }
  dfs(1,1);
  cout<<ans;
}