这道题与上一道还是有些不同的
上一道题状态设计为每个结点选或不选
在转移的时候每条边至少选一个就可以维护出当前子树中正确的选法中最小的
本题就需要更为复杂的转移了
因为你不能通过当前父结点选或不选来判断出子节点选或不选
本题要求每个结点的 父结点,子节点,本身 中的一个结点被选
因此状态表示为f[i][j]
f[i][0]//第i个结点的父结点被选
f[i][1]//第i个结点有一个子节点被选
f[i][2]//第i个节点本身被选
转移可以设计为
f[u][0] += min(f[v][1],f[v][2])
f[u][1]的转移较为复杂,只需要一个子节点被选即可,所以选择一个最好的子节点来选,具体看代码
f[u][2] += min(f[v][1],f[v][2],f[v][0]);
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1510,M = N * 2,inf = 0x3f3f3f3f;
int n,f[N][3],cost[N];//0 被父结点看到,1 被子节点看到,2放警卫
int head[N],nxt[M],ver[M],idx;
bool st[N];
void add(int u,int v)
{
nxt[++ idx] = head[u];
ver[idx] = v;
head[u] = idx;
}
void dfs(int u)
{
f[u][2] = cost[u];
int res = inf;
for(int i = head[u]; i ;i = nxt[i])
{
int v = ver[i];
dfs(v);
f[u][0] += min(f[v][1],f[v][2]);
f[u][1] += min(f[v][1],f[v][2]);
f[u][2] += min(f[v][1],min(f[v][2],f[v][0]));
res = min(res,f[v][2] - min(f[v][1],f[v][2]));
}
if(res != inf)f[u][1] += res;
if(f[u][1] == 0)f[u][1] = inf;
}
int main()
{
cin >> n;
int root = 1,xi,yi,m;
for(int i = 1;i <= n;i ++)
{
scanf("%d",&xi);
scanf("%d%d",&cost[xi],&m);
for(int j = 1;j <= m;j ++)
scanf("%d",&yi),add(xi,yi),st[yi] = 1;
}
while(st[root])root ++;
dfs(root);
cout << min(f[root][2],f[root][1]);
}