学步园

无向无环图   --- 森林；树上的dp （最后解的形式为，M * a + b） a为森林某棵树上需放置的最小灯数，b为最少一盏灯照亮的边数；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

const int maxn = 1010;
const int M    = 2000;
int n,m,pre[maxn],vis[maxn][2],d[maxn][2];
vector<int> son[maxn];
int dp(int i,int j,int fa){
if(vis[i][j]) return d[i][j];
vis[i][j]=1;  pre[i]=1;
d[i][j]=0;
if(!j){
    for(int k=0;k<son[i].size();k++) if(son[i][k]!=fa){
        int v=son[i][k];
        d[i][j]+=dp(v,1,i)+M+1;
    }
}
else {
    for(int k=0;k<son[i].size();k++) if(son[i][k]!=fa){
        int v=son[i][k];
        d[i][j]+=min(dp(v,1,i)+M,dp(v,0,i)+1);
    }
}
return d[i][j];
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        int x,y;
        for(int i=0;i<=n;i++) son[i].clear();
        for(int i=1;i<=m;i++){
            scanf("%d %d",&x,&y);
            son[x].push_back(y);
            son[y].push_back(x);
        }
        memset(pre,0,sizeof(pre));
        memset(vis,0,sizeof(vis));
        int lamp_sum=0,one_light_road=0;
        for(int i=0;i<=n;i++) if(!pre[i]){
            int num=min(dp(i,0,-1),dp(i,1,-1)+M);
            lamp_sum+=num/M;
            one_light_road+=num%M;
        }
        printf("%d %d %d\n",lamp_sum,m-one_light_road,one_light_road);
    }
}