深圳罗湖的网站建设,青岛注册公司费用,孝感织云网站建设,wordpress3D翻书效果正题 题目大意
每个物品有一个可以限制的物品#xff0c;要求一个集合内所有的物品都有一个不在集合内物品限制。求这个集合可以保护的最多物品 解题思路
类似没有上司的舞会 其实就是在基环树森林#xff0c;我们可以利用二次树形dp的方法。 先找到环#xff0c;然后强行…正题 题目大意
每个物品有一个可以限制的物品要求一个集合内所有的物品都有一个不在集合内物品限制。求这个集合可以保护的最多物品 解题思路
类似没有上司的舞会 其实就是在基环树森林我们可以利用二次树形dp的方法。 先找到环然后强行将环断开进行一次dp然后强行连上进行一次dp两个答案的最小值就得这棵树的最大物品。
其实也可以贪心这里就不放了。 code
#includecstdio
#includealgorithm
#includecstring
#define N 1000010
using namespace std;
struct node{int to,next;
}a[N];
int n,x,ans,tot,fa[N],root,f[N],g[N],ls[N],d[N],mark;
bool v[N];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void check_c(int x)//判环
{v[x]true;if(v[d[x]]) markx;else check_c(d[x]);return;
}
void dp(int x)//树形dp
{v[x]true;f[x]1;g[x]2147483647/3;if(xroot) g[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(imark||yfa[x]) continue;fa[y]x;dp(y);g[x]min(f[y],g[y]);g[x]min(g[x],f[x]f[y]-1);f[x]min(f[y],g[y]);}return;
}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,d[i]),addl(d[i],i);for(int i1;in;i){if(v[i]) continue;check_c(i);rootd[mark];dp(mark);//断开环int maxsf[mark];root0;dp(mark);//连接环ansmin(maxs,g[mark]);}printf(%d,n-ans);
}
