hdu 1054 Strategic Game（树形DP||二分图）

小记：因为之前就已经做过这道题了，然后做题的周训上，又出了这道题，我脑子里有印象肯定做过，所以这道题没去想。没做。然后今天进hoj看了下，果然提交过，A了的。又因为昨天周训训的是dp，而我看了下我提交的代码是二分图做的，而题目显然是一道非常典型的树形dp，二分图我想不起来为什么二分图的解除以2是正解，因为是训练dp所以自己又动手码了树形dp，真经典，代码都很简单，1A啊。

思路：树形dp，或者二分图。二分图还不晓得为什么最大匹配就是正解这里就不讲了，贴贴代码。讲下树形dp

dproot[ i ]表示以i为根的子树，在i上放置一个士兵，看守住整个子树需要多少士兵。

all[ i ]表示看守住整个以i为根的子树需要多少士兵。

状态转移方程：dproot[i] = 1 + ∑dproot[j] （j是i的儿子）

all[i] = min(dproot[i],∑all[j]) （j是i的儿子）

对叶子节点，初始化为dproot[i] = 1, all[i] = 0;

最后的answer就是 min(dproot[root],all[root])  (root为根节点)

树形dp代码：

#include <stdio.h>
#include <string.h>
#include <stack>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

const int MAX_ = 1510;


struct node{
    int to,next,cap;
}edge[MAX_*MAX_];

int dproot[MAX_];
int all[MAX_];
bool vis[MAX_];
int head[MAX_];
int n, M;

void add(int from,int to){
    edge[M].to = to;
    edge[M].cap = 1;
    edge[M].next = head[from];
    head[from] = M++;
}

void dfs(int x,int pre){
    dproot[x] = 1;
    int sum = 0;
    for(int i = head[x]; i+1; i = edge[i].next){
        int v = edge[i].to;
        if(pre == v)continue;
        dfs(v,x);
        sum += dproot[v];
        dproot[x] += all[v];
    }
    all[x] = min(dproot[x],sum);
}



int main() {
    int T;
    int m, k;

    while(~scanf("%d",&n)){
        M = 0;
        mst(head,-1);

        for(int i = 0; i < n; ++i){
            scanf("%d:(%d)",&m,&k);
            while(k--){
                int t;
                scanf("%d",&t);
                add(m,t);
                add(t,m);
            }
        }
        dfs(0,-1);
        printf("%d\n",min(all[0],dproot[0]));
    }
    return 0;
}

二分图代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1501
typedef struct
{
    int to,next,cap;
}E;
E edge[N*N];
int V[N];
int dis[N];
int link[N];
int n,M;

void insert(int from,int to)
{
    edge[M].to=from;
    edge[M].cap=1;
    edge[M].next=V[to];
    V[to]=M++;
}
int dfs(int k)
{
    int i,t;
    for(i=V[k]; i+1; i=edge[i].next)
    {
        t=edge[i].to;
        if(!dis[t])
        {
            dis[t]=1;
            if(link[t]==-1||dfs(link[t]))
            {
                link[t]=k;
                return 1;
            }
        }
    }
   return 0;
}
int main()
{
    int i,j,m,num,k;
    while(~scanf("%d",&n))
    {
        memset(link,-1,sizeof(link));
        memset(V,-1,sizeof(V));
        M=0;
        for(i=0; i<n; i++)
        {
            scanf("%d:(%d)",&m,&k);
            while(k--)
            {
                scanf("%d",&j);
                insert(m,j);
                insert(j,m);
            }
        }
        num=0;
        for(i=0; i<n; i++)
        {
            memset(dis,0,sizeof(dis));
            if(dfs(i))num++;
        }
        printf("%d\n",num/2);
    }
    return 0;
}