题意即求一个最小顶点覆盖。
对于没有孤立点的图G=(V,E)，最大独立集+最小顶点覆盖= V。（往最大独立集加点）
问题可以变成求树上的最大独立集合。
每个结点的选择和其父节点选不选有关，
dp(u,1)表示父节点选，这时u不可选，
dp(u,0)表示父节点不选，这时u可选可不选。
#includeusing namespace std;const int maxn = 1501;int meo[maxn][2];int vis[maxn][2], clk;int hd[maxn],nx[maxn<<1],to[maxn<<1],ec;void add(int u,int v){ to[ec] = v; nx[ec] = hd[u]; hd[u] = ec++;}int dp(int u,int a = 0,int f = -1)//a表示父节点选不选{ if(vis[u][a] == clk) return meo[u][a]; vis[u][a] = clk; int &re = meo[u][a]; re = 0; int pick = 1; for(int i = hd[u]; ~i; i = nx[i]){ int v = to[i]; if(v == f) continue; if(!a){ pick += dp(v,1,u); } re += dp(v,0,u); } if(!a) re = max(re,pick); return re;}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int n; while(~scanf("%d",&n)){ memset(hd,-1,sizeof(hd)); ec = 0; for(int i = 0; i < n; i++){ int u,sn; scanf("%d:(%d)",&u,&sn); while(sn--){ int v;scanf("%d",&v); add(u,v); add(v,u); } } clk++; printf("%d\n",n-dp(0)); } return 0;}
最小点覆盖还可以用二分匹配来做
关键代码，下面可以适合无向图，如果用有向图的算法一个匹配会算两次。
int link[maxn];int vis[maxn], clk;bool aug(int u){ if(vis[u] == clk) return false; vis[u] = clk; for(int i = hd[u]; ~i; i = nx[i]){ int v = to[i]; if(!~link[v] || aug(link[v])){ link[v] = u; link[u] = v; return true; } } return false;}int Hungary(int n){ memset(link,-1,sizeof(link)); int ans = 0; for(int i = 0; i < n; i++){ if(link[i]<0){ clk++; if(aug(i)) ans++; } } return ans;} 也可以直接dp求最小点覆盖集合，
f[u][p]表示以u为根的树最小点覆盖，p表示选不选u。
当选u的时候，子结点可选可不选，
当不选u的时候，子结点都选。
（实际上存在在某些结点只选一个子节点的最优解的情况，但是这样做并不会丢解）
int f[maxn][2],vis[maxn],clk;void dfs(int u = 0,int fa = -1){ vis[u] = clk; f[u][0] = 0; f[u][1] = 1; for(int i = hd[u]; ~i; i = nx[i]){ int v = to[i]; if(v == fa) continue; if(vis[v] != clk) dfs(v,u); f[u][1] += min(f[v][0],f[v][1]); f[u][0] += f[v][1]; }}