Description
上帝手中有 N 种世界元素，每种元素可以限制另外1种元素，把第 i 种世界元素能够限制的那种世界元素记为 A[i]。
现在，上帝要把它们中的一部分投放到一个新的空间中去建造世界。
为了世界的和平与安宁，上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素限制它。
上帝希望知道，在此前提下，他最多可以投放多少种世界元素？
第一行是一个整数N，表示世界元素的数目。
第二行有 N 个整数A[1], A[2], …, A[N]。A[i] 表示第 i 个世界元素能够限制的世界元素的编号。
一个整数，表示最多可以投放的世界元素的数目。
N≤106,1≤A[i]≤N
Solution
我们从被限制的点到限制它的点连一条边
发现每个点出度都为 1 且一共有N条边，是个内向基环树森林
对于每个环，任取环中一点 p 和 A[p] ，这棵基环树的最优答案的状态有三种情况
对于前两个，我们可以把 P 与 A[p] 的连边断开，在以 p 为根的树上做一遍dp
f[ u ][ 0/1 ] 表示 u 选了/不选的情况下以 u 为根的子树能选的最多点数
f[ u ][ 0 ]=$\sum\limits_{A[v]=u}^{}$max(f[ v ][ 0 ],f[ v ][ 1 ])
f[ u ][ 1 ]=max(f[ u ][ 0 ]-max(f[ v ][ 0 ],f[ v ][ 1 ])+f[ v ][ 0 ]) (A[v]=u)
当前答案为max(f[ p ][ 0 ],f[ p ][ 1 ])
对于后面一个，我们强制要求 p 不选，然后统计f[ A[p] ][ 1 ]时令它等于f[ A[p] ][ 0 ]+1
/以下摘自《算法竞赛进阶指南》
这种用两次树形dp代替基环树dp的方法，就是我们之前提到的“环形dp”的解决方案之一，
“两次dp，一次断开，一次强制连接（通过适当的条件和赋值实现）”。
另外，在找环时，由于每个点的入度都为 1 ，所以从下往上一直找，一定能找到一个环
（提示：ACwing上vector存边会MLE）
Code
#include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; const int N=1e6+10; int A[N],n,x,rt,f[N][2],ans,an,head[N],to[N],nxt[N],tot; bool flag[N]; void add(int x,int y) { to[++tot]=y,nxt[tot]=head[x],head[x]=tot; } void solve(int u,int pos) { int rev=-1<<30; flag[u]=1,f[u][0]=0; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(v==rt) continue; solve(v,pos); f[u][0]+=max(f[v][0],f[v][1]); rev=max(rev,f[v][0]-max(f[v][0],f[v][1])); } f[u][1]=f[u][0]+rev+1; if(u==A[rt] && pos) f[u][1]=f[u][0]+1; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i]),add(A[i],i); for(int i=1;i<=n;i++) if(!flag[i]) { x=i; while(!flag[A[x]]) flag[x]=1,x=A[x]; rt=x,solve(rt,0); an=max(f[x][0],f[x][1]); solve(rt,1); an=max(an,f[x][0]); ans+=an; } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/hsez-cyx/p/12329263.html