http://www.lydsy.com/JudgeOnline/problem.php?id=1589

?

tarjan縮環后拓撲排序上DP

?

#include<cstdio> #include<iostream> #include<algorithm>#define N 100001using namespace std;int to[N];int m; int bl[N],siz[N];int st[N],top; int id,dfn[N],low[N]; bool vis[N];int FRONT[N],TO[N],NXT[N],TOT; int in[N];int dp[N];void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }void tarjan(int x) {dfn[x]=low[x]=++id;vis[x]=true;st[++top]=x;if(!dfn[to[x]]){tarjan(to[x]);low[x]=min(low[x],low[to[x]]);}else if(vis[to[x]]) low[x]=min(low[x],dfn[to[x]]);if(dfn[x]==low[x]){++m;while(st[top]!=x) {vis[st[top]]=false;bl[st[top]]=m;siz[m]++;top--;}vis[x]=false;bl[x]=m;siz[m]++;top--;} }void add(int u,int v) {TO[++TOT]=v; NXT[TOT]=FRONT[u]; FRONT[u]=TOT;in[v]++; }void topsort() {top=0;for(int i=1;i<=m;++i){if(!in[i]) st[++top]=i;dp[i]=siz[i];} int now,t;while(top){now=st[top--];for(int i=FRONT[now];i;i=NXT[i]){t=TO[i];dp[t]+=dp[now];in[t]--;if(!in[t]) st[++top]=t;}} }int main() {int n;read(n);for(int i=1;i<=n;++i) read(to[i]);for(int i=1;i<=n;++i)if(!dfn[i]) tarjan(i);for(int i=1;i<=n;++i)if(bl[i]!=bl[to[i]]) add(bl[to[i]],bl[i]);topsort();for(int i=1;i<=n;++i) cout<<dp[bl[i]]<<'\n'; }

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/8142648.html

總結

以上是生活随笔為你收集整理的bzoj千题计划161：bzoj1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。