题目链接：

题意:给定一个森林。每个节点上安装一个灯可以覆盖与该节点相连的所有边。选择最少的节点数num覆盖所有的边。在num最小的前提下，合理放置num个灯使得被两个灯覆盖的边最多？

思路：f[u][0]表示u不放灯的最小灯数，b[u][0]表示相应的被两个灯覆盖的边的最大数。f[u][1],b[u][1]类似。

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;struct node{    int v,next;};int C,num=0;node edges[2005];int head[1005],e;int n,m,f[1005][2],b[1005][2];void Add(int u,int v){    edges[e].v=v;    edges[e].next=head[u];    head[u]=e++;}void DFS(int u,int c,int p){    if(f[u][c]!=-1) return;    f[u][c]=c;b[u][c]=0;    int i,v;    for(i=head[u];i!=-1;i=edges[i].next)    {        v=edges[i].v;        if(v==p) continue;        if(c)        {            DFS(v,1,u);            DFS(v,0,u);            if(f[v][0]
        
         b[v][1]+1)            {                f[u][c]+=f[v][0];                b[u][c]+=b[v][0];            }            else            {                f[u][c]+=f[v][1];                b[u][c]+=b[v][1]+1;            }        }        else        {            DFS(v,1,u);            f[u][c]+=f[v][1];            b[u][c]+=b[v][1];        }    }}int main(){    for(scanf("%d",&C);C--;)    {        scanf("%d%d",&n,&m);        memset(head,-1,sizeof(head));        e=0;        int i,u,v;        for(i=1;i<=m;i++)        {            scanf("%d%d",&u,&v);            Add(u,v);            Add(v,u);        }        memset(f,-1,sizeof(f));        int ans1=0,ans2=0,x0,y0,x1,y1;        for(i=0;i
         
          b[i][1])            {                ans1+=f[i][0];                ans2+=b[i][0];            }            else            {                ans1+=f[i][1];                ans2+=b[i][1];            }        }        printf("Case %d: %d %d %d\n",++num,ans1,ans2,m-ans2);    }    return 0;}