「UVA10859」Placing Lampposts

题意：给定一个 $n$ 个点 $m$ 条边的无向无环图，在尽量少的节点上放灯，使得所有边都与灯相邻(被灯照亮)。在灯的总数最小的前提下，被两盏灯同时照亮的边数应该尽可能大。

还是树形 DP。

这道题有两个限制条件：第一条件为灯的总数最小，第二条件为被两盏灯同时照亮的边数最大。

发现限制条件既包括最小又包括最大，不好转移，我们尝试改变第二个条件，即变成只被一盏灯照亮的边最小，这样两个限制条件就都是最小了。因此我们把放的灯数 $x$ 和只被一盏灯照亮的边数 $y$ 的量放在一起处理，由于第一条件比第二条件影响更大，我们把它们的花费 $m$ 设为 $kx+y$ ($k$ 是一个足够大的值，大于 $y$ 的总和，否则会使得 $y$ 影响到 $x$)，这样既可以便于直接从 $m$ 中直接得出 $x$ 和 $y$，同时也利于转移。

我们设 $f _{i,0/1}$ 表示不在/在第 $i$ 个点放灯的最小花费，那么转移方程为：

$$f _{u,0}=f _{u,0}+f _{v,1}+1\\\\ f _{u,1}=f _{u,1}+\min(f _{v,0}+1,f _{v,1})$$

第一个方程表示若 $u$ 不放灯，那么 $v$ 必须放灯，且只被一盏灯照亮的边数 $+1$；

第二个方程表示若 $u$ 放灯，那么 $v$ 放不放灯均可，不放灯时同样只被一盏灯照亮的边数 $+1$。

最后原图可能为森林，对每棵树都要 DP 一遍。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn=100010,p=5000;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int t,n,m;
int head[maxn],cnt,tot;
int f[maxn][2],vis[maxn];
vector<int> root;
struct node
{
	int next;
	int to;
}e[maxn<<1];
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void dfs(int u)
{
	vis[u]=1;
	f[u][0]=0;
	f[u][1]=p;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v])
			continue;
		dfs(v);
		f[u][0]+=f[v][1]+1;
		f[u][1]+=min(f[v][0]+1,f[v][1]);
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(vis,0,sizeof(vis));
		memset(head,0,sizeof(head));
		root.clear();
		cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b);
			add(b,a);
		}
		for(int i=1;i<=n;i++)
			if(!vis[i])
			{
				root.push_back(i);
				dfs(i);
			}
		int ans=0;
		for(int i=0;i<root.size();i++)
			ans+=min(f[root[i]][0],f[root[i]][1]);
		printf("%d %d %d\n",ans/p,m-ans%p,ans%p);
	}
	return 0;
}