SPOJ 1479 +SPOJ 666 无向树最小点覆盖 ,第二题要方案数,树形dp

题意：求一颗无向树的最小点覆盖。

本来一看是最小点覆盖，直接一下敲了二分图求最小割，TLE。

树形DP，叫的这么玄乎，本来是线性DP是线上往前\后推，而树形DP就是在树上，由叶子结点状态向根状态推。

dp[u][1/0]:表示，结点u，1：选择，0,：不选。dp值是以改点为根（目前为止，dfs遍历顺序自然决定了树的层）的已经选择点数，自然开始时不知道，对每个点,初值dp[u][0]=0、

dp[u][1]=1，回溯的时候:

1:dp[u][1]+=min(dp[v][1],dp[v][0]);该节点选择了，那么子节点可选可不选。

2:dp[u][0]+=dp[v][1];该节点没有选择，则其子节点必需选择。

#include<iostream>

#include<queue>

#include<stack>

#include<cstdio>

#include<vector>

using namespace std;

int n;

vector<vector<int> >v(100010);

int vis[100010];

int dp[100010][2];

inline int minn(int a,int b)

{

    if(a<b)return a;

    return b;

}

void dfs(int u)

{

    dp[u][0]=0;          //不放，0个

    dp[u][1]=1;         //放一个，

    for(int i=0;i<v[u].size();i++)

    {

        int vv=v[u][i];

        if(!vis[vv])

           {

               vis[vv]=1;

               dfs(vv);

          dp[u][0]+=dp[vv][1];          //回溯时加上

          dp[u][1]+=minn(dp[vv][1],dp[vv][0]);

           }

    }

}

int main()

{

    scanf("%d",&n);

    int tx,ty;

    for(int i=0;i<n-1;i++)

       {

           scanf("%d%d",&tx,&ty);

           v[tx].push_back(ty);

           v[ty].push_back(tx);

       }

       vis[1]=1;

       dfs(1);

    cout<<minn(dp[1][0],dp[1][1]);  //结果为根放与不放的状态最小值

       return 0;

}

666，求最优时候方案数，

多一个DP方程即可。

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

int n;

vector<vector<int> >v(100020);

int vis[100020];

struct state

{

    int light;

    int count;

};

state dp[100020][2];

inline int minn(int a,int b)

{

    if(a<b)return a;

    return b;

}

void dfs(int u)

{

    dp[u][0].light=0;          //不放，0个

    dp[u][1].light=1;         //放一个，

    dp[u][0].count=dp[u][1].count=1;

    for(int i=0;i<v[u].size();i++)

    {

        int vv=v[u][i];

        if(!vis[vv])

           {

               vis[vv]=1;

               dfs(vv);

          dp[u][0].light+=dp[vv][1].light;          //回溯时加上

          dp[u][1].light+=minn(dp[vv][1].light,dp[vv][0].light);

          dp[u][0].count= dp[u][0].count*dp[vv][1].count%10007;

         if(dp[vv][1].light<dp[vv][0].light)

           dp[u][1].count=dp[u][1].count*dp[vv][1].count%10007;

         else if (dp[vv][1].light>dp[vv][0].light)

           dp[u][1].count=dp[u][1].count*dp[vv][0].count%10007;

         else

           dp[u][1].count=dp[u][1].count*(dp[vv][0].count+dp[vv][1].count)%10007;

           }

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

          int tx,ty;

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

       {

           v[i].clear();vis[i]=0;

       }

       for(int i=0;i<n-1;i++)

       {

           scanf("%d%d",&tx,&ty);

           v[tx].push_back(ty);

           v[ty].push_back(tx);

        }

       vis[1]=1;

       dfs(1);

     int ans1=minn(dp[1][0].light,dp[1][1].light);  //结果为根放与不放的状态最小值

     if(dp[1][0].light<dp[1][1].light)

     {

         printf("%d %d\n",ans1,dp[1][0].count);

     }

     else if(dp[1][0].light>dp[1][1].light)

     {

         printf("%d %d\n",ans1,dp[1][1].count);

     }

     else

     {

         int ans2= (dp[1][0].count%10007+dp[1][1].count%10007)%10007;

         printf("%d %d\n",ans1,ans2);

     }

    }

       return 0;

}

巴特西

SPOJ 1479 +SPOJ 666 无向树最小点覆盖 ,第二题要方案数,树形dp

最新文章

热门文章