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

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

阅读量：5284 次

发布时间：2019-06-14

本文共 1388 字，大约阅读时间需要 4 分钟。

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

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

2.也可以用树形dp

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

/*用STL中的vector建立邻接表实现匈牙利算法效率比较高处理点比较多的效率很高。1500的点都没有问题*/#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int MAXN=1505;//这个值要超过两边个数的较大者，因为有linkerint linker[MAXN];bool used[MAXN];vector
           
            G[MAXN];int uN;bool dfs(int u){ int sz=G[u].size(); for(int i=0; i

View Code

c2.树形dp

/*HDU 1054G++ 312ms 560K*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN=1510;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=0;i