上海静安网站制作,大型网站设计首页实例,wordpress怎么去调用文章图片,wordpress 浮动导航插件正题 题目大意
每个物品有一个可以限制的物品#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);
}
