https://www.luogu.org/problemnew/show/P2921

C++版本一

樸素

一、為了實現這一方法，我們對每個點設置兩個屬性：

1、顏色?(color)(color)?： 此節點第一次被訪問時，這條訪問他的路徑是由那個節點發出的（起點）。

2、時間戳?(dfn)(dfn)?：此節點第一次被訪問時，他到發出這條路徑的起點的距離（發出節點的?dfn = 0dfn=0，第二個被訪問的節點的?dfn = 1dfn=1，第三個?dfn = 2dfn=2?......）

有了這兩個屬性，我們就可以計算環的大小，方法如下：

1、從某一節點發出路徑

2、走到某個節點上（包括起點），如果這個節點沒有被染色，那么染成自己的顏色，并標記上?dfndfn

3、走到某個節點上，如果這個節點已經被染成了自己的顏色，那么環的大小就出來了：當前時間?(cnt)(cnt)?-??此節點?dfndfn

到了這一步，實際上已經解決了另一個更簡單的問題：NOIP2015 信息傳遞。 接下來就是本題特色了

二、對于每一只奶牛（或者說每一個起點、顏色、路徑），我們記錄如下兩個屬性：

1、環的大小?(minc)(minc)?：每條路徑最終都會進入環中，或者起點本身就在環中，我們記錄下這個環的大小為之后服務

2、入環時間戳?(sucdfn)(sucdfn)?：這條路徑什么時候會進入環中，同樣是為之后服務的一個屬性

首先講解一下如果得到這兩個屬性：

1、在上一節中我們已經講了如何初步獲取環的大小，入環時間戳只要記錄為那個交點的時間戳即可

2、如果走到了之前走過的節點，那么新的路徑必然進入之前路徑的環中，直接把這個環的大小要過來就行了。入環時間戳則分兩種情況：

i. 如果這個節點不在環中，“原路徑的入環時間戳?-??原路徑中此節點的時間戳 +　新路徑當前時間”　即為新路徑的入環時間戳;

ii. 而如果這個節點在環中，直接就是新路徑當前時間。

iii. 判斷方法則是 “原路徑的入環時間戳?-??原路徑中此節點的時間戳” 是否大于?00，綜合起來就是：“max(max(原路徑的入環時間戳?-??原路徑中此節點的時間戳, \;0),0)?+　新路徑當前時間”

三、把上面的問題都解決了，出答案就太簡單了：

1、第一節中的發現環的大小之后，答案就是“當前時間”

2、第二節中與之間走過的節點相遇并記錄完信息后，答案是 “入環時間戳 + 環的大小”

至此本題已經完美解決，且沒有用到任何算法。貼代碼：

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=200000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans,cnt,flag,temp,sum; int a[N]; int dist[N]; int color[N]; int dfn[N]; int sucdfn[N]; char str; int minc[N]; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int cow = 1; cow <= n; ++cow){for(int i = cow, cnt = 0; ; i = a[i], ++cnt){if(!color[i]) {color[i] = cow;dfn[i] = cnt;}else if(color[i] == cow) {minc[cow] = cnt - dfn[i];sucdfn[cow] = dfn[i];cout << cnt << endl;break;}else {minc[cow] = minc[color[i]];sucdfn[cow] = cnt + max(sucdfn[color[i]] - dfn[i], 0);cout << sucdfn[cow] + minc[cow] << endl;break;}}}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

強連通分量SCC

參考文章：https://blog.csdn.net/weixin_43272781/article/details/88557457

#include<bits/stdc++.h> using namespace std; const int Maxn=100005; int next[Maxn]; int ans[Maxn]; int head[Maxn],cnt; struct road {int to,next; }e[Maxn*2]; void add(int a,int b) {cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt; } int sum,color[Maxn],low[Maxn],ins[Maxn],tim[Maxn],sta[Maxn],top=1,col; int Lemon[Maxn]; void Tarjan(int x) {sum++;tim[x]=low[x]=sum;sta[top]=x;top++;ins[x]=1;for(int i=head[x];i!=0;i=e[i].next){if(ins[e[i].to]==0){Tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}else if(ins[e[i].to]==1)low[x]=min(low[x],tim[e[i].to]);}if(tim[x]==low[x]){col++;do{top--;color[sta[top]]=col;ins[sta[top]]=-1;}while(sta[top]!=x);}return ; } void search(int root,int x,int step) {if(ans[x]!=0) {ans[root]=ans[x]+step;return ;}else search(root,next[x],step+1); } int main() {int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d",&next[i]);add(i,next[i]);if(next[i]==i) ans[i]=1;//注意特判環為1的情況。}for(int i=1;i<=n;i++)if(ins[i]==0) Tarjan(i);for(int i=1;i<=n;i++)Lemon[color[i]]++;//記錄環的大小for(int i=1;i<=n;i++)if(Lemon[color[i]]!=1) ans[i]=Lemon[color[i]];//處理在環內的點for(int i=1;i<=n;i++)if(ans[i]==0) search(i,next[i],1);//處理在環外的點。for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0; }

C++版本三

#include<cstdio> #include<iostream> using namespace std; const int N=1e5+5; int n,to[N],rd[N],w[N],dep[N],mk[N];char vis[N],ins[N]; int dfs(int x){int t=to[x];vis[x]=ins[x]=1;if(!vis[t]){dep[t]=dep[x]+1;w[x]=dfs(t);w[x]+=(mk[t]?(mk[x]=(mk[x]!=2?1:0),0):1);}else if(ins[t])w[x]=dep[x]-dep[t]+1,mk[x]=1,mk[t]=(x==t?0:2);else w[x]=w[t]+1;ins[x]=0;return w[x]; } int main(){ios::sync_with_stdio(false);cin>>n;int x;for(int i=1;i<=n;++i)cin>>to[i],++rd[to[i]];for(int i=1;i<=n;++i)if(!rd[i])w[i]=1,dfs(i);for(int i=1;i<=n;++i)if(!vis[i])dfs(i);//totally a cyclefor(int i=1;i<=n;++i)cout<<w[i]<<endl;return 0; }

C++版本四

題解：

拓撲排序刪鏈 → 對環上的點計算答案 → dfs計算其他點的答案。

環上的點答案都一樣，可以一遍dfs跑出來；

其他點的答案在dfs返回的時候+1即可。

#include <cstdio> #define maxn 100010int next[maxn], in[maxn], ans[maxn]; bool vis[maxn];void del(int cur) {vis[cur] = true;in[next[cur]]--;if(!in[next[cur]]) del(next[cur]); }int calccircle(int cur, int depth) {ans[cur] = depth;if(ans[next[cur]]) return depth;else return ans[cur] = calccircle(next[cur], depth + 1); }int calc(int cur) {if(ans[cur]) return ans[cur];else return ans[cur] = calc(next[cur]) + 1; }int main() {int n;scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", next + i), in[next[i]]++;for(int i = 1; i <= n; i++) if(!in[i] && !vis[i]) del(i);for(int i = 1; i <= n; i++) if(in[i] && !ans[i]) calccircle(i, 1);for(int i = 1; i <= n; i++) if(!in[i] && !ans[i]) calc(i);for(int i = 1; i <= n; i++) printf("%d\n", ans[i]); }

?

總結

以上是生活随笔為你收集整理的[USACO08DEC]在农场万圣节Trick or Treat on the Farm的全部內容，希望文章能夠幫你解決所遇到的問題。

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