给你一个 n 个点 m 条边的无向无环图， 在尽量少的结点上放灯， 使得
所有边都被照亮。 每盏灯将照亮以它为一个端点的所有边。 在灯的总数
最小的前提下， 被两盏灯同时照亮的边数应尽量大。
【输入格式】
输入的第一行为测试数据组数 T （ T≤30 ） 。 每组数据第一行为两个整
数 n 和 m （ m ＜ n≤1000 ） ， 即点数（所有点编号为 0 ～ n － 1 ） 和边数； 以下
m 行每行为两个不同的整数 a 和 b ， 表示有一条边连接 a 和 b （ 0≤a ， b≤n ） 。
【输出格式】
对于每组数据， 输出 3 个整数， 即灯的总数、 被两个灯照亮的边数和
只被一个灯照亮的边数。
【分析】
无向无环图的另一个说法是 “ 森林 ” ， 它由多棵树组成。 动态规划是解
决树上的优化问题的常用工具， 本题就是一个很好的例子。
首先， 本题的优化目标有两个： 放置的灯数 a 应尽量少， 被两盏灯同
时照亮的边数 b 应尽量大。 为了统一起见， 我们把后者替换为： 恰好被一
盏灯照亮的边数 c 应尽量小， 然后改用 x ＝ Ma ＋ c 作为最小化的目标， 其中
M 是一个很大的正整数。 当 x 取到最小值时， x/M 的整数部分就是放置的灯
数的最小值； x ％ M 就是恰好被一盏灯照亮的边数的最小值。
一般来说， 如果有两个需要优化的量 v
1 和 v 2 ， 要求首先满足 v 1 最小，
在 v
1 相同的情况下 v 2 最小， 则可以把二者组合成一个量 Mv 1 ＋ v 2 ， 其中 M 是
一个比 “v
2 的最大理论值和 v 2 的最小理论值之差 ” 还要大的数。 这样， 只要
两个解的 v
1 不同， 则不管 v 2 相差多少， 都是 v 1 起到决定性作用； 只有当 v 1 相
同时， 才取决于 v
2 。 在本题中， 可以取 M ＝ 2000 [9] 。
每棵树的街灯互不相干， 因此可以单独优化， 最后再把答案加起来
即可。 下面我们只考虑一棵树的情况。 首先对这棵树进行 DFS ， 把无根树
转化为有根树， 然后试着设状态 d （ i ） 为以 i 为根的子树的最小 x 值， 看看
能不能写出状态转移方程。
决策只有两种： 在 i 处放灯和不在 i 处放灯。 后继状态是 i 的各个子结
点。 可是问题来了： i 处是否放灯将影响到其子结点的决策。 因此， 我们
需要把 “ 父结点处有没有放灯 ” 加入状态表示中。 新状态为： d （ i ， j ） 表
示 i 的父结点 “ 是否放灯 ” 的值为 j （ 1 表示放灯， 0 表示没放） ， 以 i 为根的树
的最小 x 值（算上 i 和其父结点这条边） 。
注意到各子树可以独立决策， 因此可作出如下决策。
决策一： 结点 i 不放灯。 必须 j ＝ 1 或者 i 是根结点时才允许作这个决
123
策。 此时 d （ i ， j ） 等于 sum ｛ d （ k ， 0 ） ｜ k 取遍 i 的所有子结点｝ 。 如果 i
不是根， 还得加上 1 ， 因为结点 i 和其父结点这条边上只有一盏灯照亮。
决策二： 结点 i 放灯。 此时 d （ i ， j ） 等于 sum ｛ d （ k ， 1 ） ｜ k 取遍 i 的
所有子结点｝ ＋ M 。 如果 j ＝ 0 且 i 不是根， 还得加上 1 ， 因为结点 i 和其父结
点这条边只有一盏灯照亮。
用数学式子很难表达上面的状态转移， 但用程序表达却可以很清
晰
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mn=1005,mm=2005;
struct node
{
int to,next;
} edge[mm];
int n,m,head[mn],vis[mm][2],d[mm][2],tot;
void add(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
int dp(int i,int j,int f)
{
if(vis[i][j]) return d[i][j];
vis[i][j]=1;
//一定可以放的
int& ans=d[i][j];
ans=2000;
if(~f&&j==0) ans++;
for(int k=head[i]; ~k; k=edge[k].next)
{
int u=edge[k].to;
if(u!=f)
ans+=dp(u,1,i);
}
if(f==-1||j==1)
{
int sum=0;
for(int k=head[i]; ~k; k=edge[k].next)
{
int u=edge[k].to;
if(u!=f)
sum+=dp(u,0,i);
}
if(~f) sum++;//总是容易漏掉一些东西。。。
ans=min(ans,sum);
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
tot=0;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
memset(vis,0,sizeof(vis));
int ans=0;
for(int i=0; i<n; i++)
if(!vis[i][0])
ans+=dp(i,0,-1);
printf("%d %d %d\n",ans/2000,m-ans%2000,ans%2000);
}
return 0;
}