HDU - 1054 Strategic Game（二分图最小点覆盖/树形dp）

d.一颗树，选最少的点覆盖所有边

s.

1.可以转成二分图的最小点覆盖来做。不过转换后要把匹配数除以2，这个待细看。

2.也可以用树形dp

c.匈牙利算法（邻接表，用vector实现）：

/*

用STL中的vector建立邻接表实现匈牙利算法

效率比较高

处理点比较多的效率很高。1500的点都没有问题

*/

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<vector>

using namespace std;

const int MAXN=;//这个值要超过两边个数的较大者，因为有linker

int linker[MAXN];

bool used[MAXN];

vector<int>G[MAXN];

int uN;

bool dfs(int u)

{

    int sz=G[u].size();

    for(int i=; i<sz; i++)

    {

        if(!used[G[u][i]])

        {

            used[G[u][i]]=true;

            if(linker[G[u][i]]==-||dfs(linker[G[u][i]]))

            {

                linker[G[u][i]]=u;

                return true;

            }

        }

    }

    return false;

}

int hungary()

{

    int u;

    int res=;

    memset(linker,-,sizeof(linker));

    for(u=; u<uN; u++)

    {

        memset(used,false,sizeof(used));

        if(dfs(u)) res++;

    }

    return res;

}

int main(){

    int n,k;

    int u,v;

    int i,j;

    while(~scanf("%d",&n)){

        for(i=;i<MAXN;++i){

            G[i].clear();

        }

        for(i=;i<n;++i){

            scanf("%d:(%d)",&u,&k);

            for(j=;j<k;++j){

                scanf("%d",&v);

                G[u].push_back(v);

                G[v].push_back(u);

            }

        }

        uN=n;

        printf("%d\n",hungary()/);

    }

    return ;

}

c2.树形dp

/*

HDU 1054

G++ 312ms 560K

*/

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN=;

struct Node

{

    int father,brother,child;

    int yes;//该结点放置

    int no;//该结点不放置

}t[MAXN];

void DFS(int x)

{

    int child=t[x].child;

    while(child)

    {

        DFS(child);

        t[x].yes+=min(t[child].yes,t[child].no);

        //父亲结点放置了，儿子结点可以放置也可以不放置

        t[x].no+=t[child].yes;

        //父亲结点没有放置，儿子结点必须放置

        child=t[child].brother;

    }

}

bool used[MAXN];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n;

    int root,k,v;

    while(scanf("%d",&n)!=EOF)

    {

        memset(used,false,sizeof(used));

        int Root;//根结点

        for(int i=;i<n;i++)

        {

            scanf("%d:(%d)",&root,&k);

            root++;//编号从1开始

            if(i==)Root=root;

            if(!used[root])

            {

                used[root]=true;

                t[root].brother=t[root].father=t[root].child=;

                t[root].yes=;

                t[root].no=;

            }

            while(k--)

            {

                scanf("%d",&v);

                v++;

                if(!used[v])

                {

                    used[v]=true;

                    t[v].brother=t[v].father=t[v].child=;

                    t[v].yes=;

                    t[v].no=;

                }

                t[v].brother=t[root].child;

                t[v].father=root;

                t[root].child=v;

            }

        }

        DFS(Root);

        printf("%d\n",min(t[Root].yes,t[Root].no));

    }

    return ;

}