题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4126
$LRJ$紫书例题$9-26$
题目大意:
给定一颗树 有些边已经标好方向 现在要给其余的边标上方向 使得最长的有向链最短
$HIT:$ 题目额外给了一个结论 假设已经确定方向的边所能得到的最长链为$k$ 最后的最长链一定$k$ 或$k + 1$
不知道是自己太久没有写树形$DP$还是这题的确比较麻烦 花了好久才折腾出来
首先 利用题目给的结论 我们实际上只需要解决以下这个几乎等价的问题
判断所给的树是否可以构造出最长链不超过$k$的方案
如果是的 那么最长链就是$k$否则为$k + 1$
对于这个可行解问题 我们可以这样考虑
对于每颗子树的最长链 它要么经过这颗子树的根节点 要么在这个根节点的某个儿子所对应的子树中
因此只需递归地去检验每颗子树是否合法即可
我们可以建立三个数组 $f[x][y]$ $up[x]$ $down[x]$
$f[x][y]$代表 到达该根节点$x$的向上的最长链最小值为$y$时向下的最长链最小值为多少
$up[x]$ $down[x]$分别代表该根节点向上/下的最长链的最小值
然后由于数据范围比较小 所以可以直接用这种$O(n^2)$的方法轻松解决
#include <bits/stdc++.h>
using namespace std;
const int N = , E = N << ;
int firste[N], nexte[E], v[E], w[E];
int n, e, ans;
void build(int x, int y, int z)
{
nexte[++e] = firste[x];
firste[x] = e;
v[e] = y;
w[e] = z;
}
void init(int uu)
{
int vv;
char ch;
n = ;
e = ;
memset(firste, , sizeof firste);
ans = ;
do
{
n = max(n, uu);
while(scanf("%d%c", &vv, &ch), vv)
{
n = max(n, vv);
if(ch == 'd')
{
build(uu, vv, );
build(vv, uu, );
}
else if(ch == 'u')
{
build(uu, vv, );
build(vv, uu, );
}
else
{
build(uu, vv, );
build(vv, uu, );
}
}
}while(scanf("%d", &uu), uu);
}
void dfs0(int u, int fa, int dist)
{
ans = max(ans, dist);
for(int p = firste[u]; p; p = nexte[p])
if(w[p] && v[p] != fa)
dfs0(v[p], u, dist + );
}
int f[N][N], up[N], down[N];
bool dfs(int u, int fa)
{
for(int p = firste[u]; p; p = nexte[p])
if(v[p] != fa)
{
if(!dfs(v[p], u))
return ;
if(w[p])
{
for(int i = ; i <= min(down[v[p]], ans); ++i)
f[u][i] = ans + ;
}
else if(w[p ^ ])
{
for(int i = ; i <= ans; ++i)
f[u][i] = max(f[u][i], up[v[p]] + );
}
else
{
for(int i = ; i <= down[v[p]]; ++i)
f[u][i] = max(f[u][i], up[v[p]] + );
}
}
bool re = ;
for(int i = ; i <= ans; ++i)
if(f[u][i] + i <= ans)
{
re = ;
down[u] = min(down[u], i);
up[u] = min(up[u], f[u][i]);
}
return re;
}
int main()
{
int tmp;
while(scanf("%d", &tmp), tmp)
{
init(tmp);
for(int i = ; i <= n; ++i)
dfs0(i, i, );
memset(f, , sizeof f);
memset(down, 0x3f, sizeof down);
memset(up, 0x3f, sizeof up);
if(dfs(, ))
printf("%d\n", ans + );
else
printf("%d\n", ans + );
}
return ;
}