题目链接
https://vjudge.net/problem/UVA-10859
题意
给你一个n个点m条边的无向无环图，在尽量上的结点上放灯，使得所有边都被照亮。每盏灯都会照亮以它为端点的所有边，要求灯尽量少且被俩盏灯照亮的边尽量多。
分析
这个题有两个最优化条件，灯数a尽量小，被两盏灯照亮的边b尽量大。先把条件转化为尽量小，被一盏灯照亮的边c尽量小；这样，我们就可以用一个变量x=Ma+c来同时控制两个条件，只要x尽量小就好了。其中M的值要比c的理论最大值减理论最小值之差还要大。因为a的优先级高于c，所以a减少一个带来的值的减少要比c无论如何减少带来的值的减少都要多才行。
注意到给定的是一个无向无环图，也就是说是一个”森林“，树与树之间的状态互不影响；所以我们可以先求每一个树的最小x值，然后累加即可。
对于树形dp，我们不好画出其状态转移图，我们通过建立有根树来分析状态转移。也就是说，在状态转移图中，结点的状态就只是当前结点的状态；而在有根树中，结点的状态是指以当前结点为根的子树的状态。
确定好状态后，就是给这个状态赋一个含义。设d(i)表示以i为根的子树所得到的最小x值。接着就是确定状态转移方程，写转移方程的过程中，我们发现d(i)的值不只与子结点有关，还与父节点有关，所以我们再引入一个量j，表示i的父节点有没有放灯。j为1表示放了灯。
对于当前结点i，对它处理有两种策略：放灯和不放灯。
（1）放灯
显然，对于任意结点，这都是一个合法策略。
d(i,j)=sum{d(k,1) | k为i的子结点}，如果i不是根且j的值为0，那么d(i,j)的值要加一。因为i与i的父节点这条边是被一盏灯照亮的边。
（2）不放灯
只有当i是根或者i的父节点放了灯，这才是一个合法策略。
d(i,j)=sum{d(k,0) | k为i的子结点}，如果i的父节点放了灯，那么d(i,j)的值要加一。
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>using namespace std;const int maxn=1e3+100;
vector<int> g[maxn];
int vis[maxn][2],d[maxn][2];int dfs(int i,int j,int f) //i为当前结点，j为父节点的状态，f为父节点
{if(vis[i][j])return d[i][j];vis[i][j]=1;//放灯int ans=2000; //M值为2000，放灯a加1，值加2000for(int u=0; u<g[i].size(); u++){int v=g[i][u];if(v!=f) //注意除去父节点{ans+=dfs(v,1,i);}}if(j==0 && f>=0)ans++;//不放灯if(f<0 || j){int sum=0;for(int u=0; u<g[i].size(); u++){int v=g[i][u];if(v!=f)sum+=dfs(v,0,i);}if(f>=0)sum++;ans=min(ans,sum);}d[i][j]=ans;return ans;
}int main()
{int T;scanf("%d",&T);while(T--){int n,m;memset(vis,0,sizeof(vis));scanf("%d%d",&n,&m);for(int i=0; i<n; i++)g[i].clear();for(int i=0; i<m; i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}int ans=0;for(int i=0; i<n; i++)if(!vis[i][0])ans+=dfs(i,0,-1);printf("%d %d %d\n",ans/2000,m-ans%2000,ans%2000);}return 0;}