观察题目可以发现每个结点有选和不选两种状态
状态可以表示为f[i][j]
f[i][0]表示不选当前结点
f[i][1]表示选择当前结点
因为每条边都要被观察到
所以父结点不选子节点一定要选
父结点选子节点可以选或不选
表示为转移方程就是
f[u][0] += f[v][1];
f[u][1] += min(f[v][1],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][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][0] = 0;
f[u][1] = 1;
for(int i = head[u]; i ;i = nxt[i])
{
int v = ver[i];
dfs(v);
f[u][1] += min(f[v][0],f[v][1]);
f[u][0] += f[v][1];
}
}
int main()
{
while(~scanf("%d",&n))
{
memset(head,0,sizeof head);
memset(st,0,sizeof st);
idx = 0;
int xi,yi,size,root = 0;
for(int i = 0;i < n;i ++)
{
scanf("%d:(%d)",&xi,&size);
for(int j = 1;j <= size;j ++)
scanf("%d",&yi),add(xi,yi),st[yi] = 1;
}
while(st[root])root ++;
dfs(root);
printf("%d\n",min(f[root][0],f[root][1]));
}
}
应该可以以任意一个节点为根做dfs,结果都是一样的,不需要这么麻烦找根
我觉得好像不太行。
如果可以的话,那最后的答案存在哪里?
min(f[x][0],f[x][1]);
换句话来说 x是什么
这样子好像可以啊 AC了
因为你存了双向边