题目链接：点击打开链接
题意：给你一个n个点m条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮，每盏灯将照亮以它为一个端点的所有边。在灯的总数最小的前提下，被两盏灯同时照亮的边数应尽量大。
思路：无向无环图的另一个说法是“森林”，即由多棵树组成，我们可以先算一棵树上的答案，然后累加起来就行了。本题的优化目标有两个：放置的灯数应尽量少，被两盏灯照亮的边数b应尽量大。为了统一起见，我们把后者替换为：恰好被一盏灯照亮的边数c应尽量少，然后用x=M*a+c作为最小化的目标，其中M是一个很大的正整数。当x取到最小值时，x/M的整数部分就是放置的灯数的最小值；x%M就是恰好被一盏灯照亮的边数的最小值。
下面的思路和白书上有点不同：
我们可以用dp[i][j]表示点i的状态为j时，以点i为根节点的最小x，那么如果j是1，子节点的状态既可以是0，也可以是1，如果j是0，那么子节点的状态只能是1。vector<int>vec存边比邻接表方便很多啊..
还有一点要注意，如果当前求的树只有一个节点，那么不用把在这个点上放灯，因为题目只要求把边照亮。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double ldb;
#define inf 99999999
#define pi acos(-1.0)
#define maxn 2010
#define M 2000
vector<int>vec[maxn];
vector<int>::iterator it;
int dp[maxn][2];
int vis[maxn];
void dfs(int u,int father,int f)
{
int i,j,x,v;
vis[u]=1;
dp[u][1]=dp[u][0]=inf;
if(vec[u].size()==0){
dp[u][1]=dp[u][0]=0;return;
}
if(vec[u].size()==1 && vec[u][0]==father){
if(f==0){
dp[u][1]=M;
}
else if(f==1){
dp[u][0]=0;
dp[u][1]=M;
}
}
else{
if(f==0){
dp[u][1]=M;
for(i=0;i<vec[u].size();i++){
if(vec[u][i]==father)continue;
v=vec[u][i];
dfs(v,u,1);
dp[u][1]+=min(dp[v][1],dp[v][0]+1);
}
}
else if(f==1){
dp[u][1]=M;
for(i=0;i<vec[u].size();i++){
if(vec[u][i]==father)continue;
v=vec[u][i];
dfs(v,u,1);
dp[u][1]+=min(dp[v][1],dp[v][0]+1 );
}
dp[u][0]=0;
for(i=0;i<vec[u].size();i++){
if(vec[u][i]==father)continue;
v=vec[u][i];
dfs(v,u,0);
dp[u][0]+=dp[v][1]+1;
}
}
}
}
int main()
{
int n,m,i,j,T,c,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
vec[i].clear();
}
for(i=1;i<=m;i++){
scanf("%d%d",&c,&d);
c++;d++;
vec[c].push_back(d);
vec[d].push_back(c);
}
for(i=1;i<=n;i++)vis[i]=0;
int x=0;
for(i=1;i<=n;i++){
if(vis[i])continue;
dfs(i,0,1);
x+=min(dp[i][0],dp[i][1]);
}
printf("%d %d %d
",x/2000,m-x%2000,x%2000);
}
return 0;
}