uva 10859 - Placing Lampposts dp

题意：

　　有n个节点，m条边，无向无环图，求最少点覆盖，并且在同样点数下保证被覆盖两次的变最多

分析：

1.统一化目标，本题需要优化目标有两个，一个最小灯数a，一个最大双覆盖边数b，一大一小，应该归一成，a及单覆盖边数c，\( x=Ma+c \) 为最小化目标，\( M>\Delta c \)

2.决策分析，只有两种放灯与不放，如不放灯则需要父节点必须放灯，故需要父节点状态，设\( f(i,j) \)为节点i在父节点状态为j时的最小x值，j为0代表不放灯，j为1代表放

　　\begin{cases}
    sum\{d(k,0)|k为i所有子节点\}+(i为根节点?0:1)&,i不放灯\\
    sum\{d(k,1)|k为i所有子节点\}+M+(i不为根节点且j==0?1:0)&,i\ 放灯
    \end{cases}

代码如下

 /*

 author:jxy

 lang:C/C++

 university:China,Xidian University

 **If you need to reprint,please indicate the source**

 */

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int n,m;

 int first[];

 int Next[],U[];

 bool vis[][];

 int ans[][];

 int cnt;

 int M=<<;

 void add(int u,int v) //双向边

 {

     Next[cnt]=first[u]; first[u]=cnt; U[cnt++]=v;

     Next[cnt]=first[v]; first[v]=cnt; U[cnt++]=u;

 }

 int dfs(int i,int j,int f)//i为当前节点，j为0代表父节点没放灯，为1代表放灯,f为-1代表根节点

 {

     if(vis[i][j])return ans[i][j];

     vis[i][j]=;

     int k,&Ans=ans[i][j],ans0=;

     Ans=;

     for(k=first[i];~k;k=Next[k])

     {

         if(U[k]==f)continue;

         Ans+=dfs(U[k],,i);//放灯

     }

     Ans+=M;

     if(~f)

     {

         if(j)ans0++;

         else Ans++;

     }

     if(j||f==-)

     {

         for(k=first[i];~k;k=Next[k])

         {

             if(U[k]==f)continue;

             ans0+=dfs(U[k],,i); //不放灯

         }

         Ans=min(Ans,ans0);

     }

     return Ans;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     int i,u,v;

     while(T--)

     {

         cnt=;

         memset(vis,,sizeof(vis));

         memset(first,-,sizeof(first));

         scanf("%d%d",&n,&m);

         for(i=;i<m;i++)

         {

             scanf("%d%d",&u,&v);

             add(u,v);

         }

         int Ans=;

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

         {

             if(!vis[i][])

                 Ans+=dfs(i,,-);

         }

         printf("%d %d %d\n",Ans>>,m-(Ans&(M-)),Ans&(M-));//Ans/M,m-Ans%M,Ans%M

     }

 }