上次说了说树形dp的入门
那么这次该来一点有难度的题目了：
UVA10859 Placing Lampposts
给定一个n个点m条边的无向无环图，在尽量少的节点上放灯，使得所有边都与灯相邻（被灯照亮）。
在灯的总数最小的前提下，被两盏灯同时照亮的边数应该尽可能大。
输入格式
第一行输入T,为数据组数。
每组数据第一行输入n，m，分别为该组数据中图的点数和边数。
以下m行，输入各边的两端点u，v。
输出格式
输出共T行。
对每组数据，一行输出三个数，最小灯数、被两盏灯同时照亮的边数、只被一盏灯照亮的边数。
n<=1000
有向无环图说白了就是一个森林（可以自己画图看看），第一问这不就是裸的树形dp求最大独立集吗？在每个森林上跑一遍树形dp就行。不过第二问第三问倒有点意思，怎么维护两边都放灯的道路的数量呢？这里介绍一个十分巧妙的方法，由于n<=1000,我们就可以把一个节点的权值设为比1000大的数，然后在转移的时候，如果这条路的两端节点没有都选，那么就+1，代表有多少只被一盏灯照亮的路，最后的答案除以k就是第一问，mod k就是第三问，用m减第三问的答案就是第二问。
void dfs(int x)
{
dp[x][]=k;//这里的k我们设为大于1000的数
dp[x][]=;
d[x]=;
for(int i=last[x];i;i=g[i].next)
{
int v=g[i].to;
if(d[v]) continue;
dfs(v);
dp[x][]+=min(dp[v][]+,dp[v][]);
dp[x][]+=dp[v][]+;//如果只被一盏灯照亮就加上1，目的是和被两盏灯同时照亮的边区分，同时也保证了被两盏灯同时照亮的边数应该尽可能大，毕竟我们取最小值。
}
}
经过这样一番神奇的操作，我们就成功的切掉了这道看似有点神仙的题目。
说了这么多，怎么能没有代码呢？
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#define maxn 3005
using namespace std; struct edge
{
int next;
int to;
}g[maxn]; inline int read()
{
char c=getchar();
int res=,x=;
while(c<''||c>'')
{
if(c=='-')
x=-;
c=getchar();
}
while(c>=''&&c<='')
{
res=res*+(c-'');
c=getchar();
}
return x*res;
} int t,n,m,num,aa,bb,ans;
int k=;
int last[maxn],dp[maxn][],d[maxn]; inline void add(int from,int to)
{
g[++num].next=last[from];
g[num].to=to;
last[from]=num;
} void dfs(int x)
{
dp[x][]=k;
dp[x][]=;
d[x]=;
for(int i=last[x];i;i=g[i].next)
{
int v=g[i].to;
if(d[v]) continue;
dfs(v);
dp[x][]+=min(dp[v][]+,dp[v][]);
dp[x][]+=dp[v][]+;
}
} int main()
{
t=read();
while(t--)
{
n=read();m=read();
num=;ans=;
memset(last,,sizeof(last));
memset(dp,,sizeof(dp));
memset(d,,sizeof(d));
for(int i=;i<=m;i++)
{
aa=read();bb=read();
add(aa,bb);
add(bb,aa);
}
for(int i=;i<=n;i++)
{
if(!d[i])
{
dfs(i);
ans+=min(dp[i][],dp[i][]);
}
}
printf("%d %d %d\n",ans/k,m-(ans%k),ans%k);
}
}
下面再来看这样的一道简（shen）单（xian）题
UVA1220 Hali-Bula的晚会 Party at Hali-Bula
公司里有n(n<=200)个人形成一个树状结构，即除了老板之外每个员工都有唯一的直属上司。要求选尽量多的人，但不能同时选择一个人和他的直属上司。问：最多能选多少人，以及在人数最多的前提下方案是否唯一。
输入：第一行一个数n;第二行输入老板的名字;以下的n-1行中,每行是一位员工的名字和其直属上司的名字(英文单词,长度为1到100),两个名字之间有空格隔开,'0'为输入结束的标识符。
输出：一行,输出一个数字，表示最大的访客数量。并再同一行输出单词'Yes'或'No'，代表目前方案是否唯一。
这个的第一问好像有点简单的样子，但是这第二问好像有点毒瘤啊。我们不妨从状态转移上入手，
dp[x][]+=dp[v][];
dp[x][]+=max(dp[v][],dp[v][]);
不难发现，如果 dp[v][1]==dp[v][0] 那么不就会出现两种方式了吗，因此我们用c数组来维护一下方案书是否唯一就行了，我们先判断孩子的方案数是否唯一，再用孩子去更新父亲，因为如果孩子的方案数不唯一，那么由这个孩子转移后的父亲肯定方案数也不唯一，这样就可以愉快的树形dp了。
像这样：
if(dp[v][]>dp[v][]&&c[v][])
{
c[x][]=;
}
if(dp[v][]>dp[v][]&&c[v][])
{
c[x][]=;
}
if(dp[v][]==dp[v][])
{
c[x][]=;
}
if(c[v][])
{
c[x][]=;
}
最后怎么少得了完整ac代码呢？
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#define maxn 2005
using namespace std; struct edge
{
int next;
int to;
}g[maxn]; inline int read()
{
char c=getchar();
int res=,x=;
while(c<''||c>'')
{
if(c=='-')
x=-;
c=getchar();
}
while(c>=''&&c<='')
{
res=res*+(c-'');
c=getchar();
}
return x*res;
} int n;
string aa,bb,root;
int cnt;
int num;
int last[maxn],dp[maxn][],d[maxn],c[maxn][];
map<string,int>a; inline void add(int from,int to)
{
g[++num].next=last[from];
g[num].to=to;
last[from]=num;
} void dfs(int x)
{
d[x]=;
dp[x][]=;
dp[x][]=;
for(int i=last[x];i;i=g[i].next)
{
int v=g[i].to;
if(!d[v])
{
dfs(v);
dp[x][]+=dp[v][];
dp[x][]+=max(dp[v][],dp[v][]);
if(dp[v][]>dp[v][]&&c[v][])
{
c[x][]=;
}
if(dp[v][]>dp[v][]&&c[v][])
{
c[x][]=;
}
if(dp[v][]==dp[v][])
{
c[x][]=;
}
if(c[v][])
{
c[x][]=;
}
}
}
} int main()
{
while()
{
n=read();
if(n==) break;
cnt=;num=;
memset(last,,sizeof(last));
memset(dp,,sizeof(dp));
memset(d,,sizeof(d));
memset(c,,sizeof(c));
a.clear();
for(int i=;i<=n;i++)
{
if(i==)
{
cin>>root;
a[root]=++cnt;
}
else
{
cin>>aa>>bb;
if(!a[aa])
{
a[aa]=++cnt;
}
if(!a[bb])
{
a[bb]=++cnt;
}
add(a[aa],a[bb]);
add(a[bb],a[aa]);
}
}
dfs();
printf("%d ",max(dp[][],dp[][]));
if(dp[][]==dp[][]||(dp[][]<dp[][]&&c[][])||(dp[][]>dp[][]&&c[][]))
printf("No\n");
else printf("Yes\n");
}
}
No man or woman is worth your tears, and the one who is, won't make you cry.
--snowy
2019-01-15 18:48:21