[USACO08DEC]在农场万圣节Trick or Treat on the Farm

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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。