P2921 [USACO08DEC] Trick or Treat on the Farm G 做题学习记录

题目连接

暴力搜索

起初看到这个问题，第一想法认为它非常容易。用nxt数组记录牛下一步要前往的编号，再开一个vis数组记录牛走过的房间，对于每一个房间的牛都进行dfs，走到之前被vis数组标记的房间就结束dfs，返回值就是答案
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
int n,nxt[mx];
bool vis[mx];
int find(int i,int now){
	if(vis[nxt[i]]) return now+1;
	vis[i]=true;
	return find(nxt[i],now+1);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>nxt[i];
	for(int i=1;i<=n;i++){
		memset(vis,false,sizeof(vis));
		vis[i]=true;
		cout<<find(i,0)<<endl;
	} 
}

然后就喜提30分…TLE
于是发现了复杂度实在挺高，虽然不知道怎么算这个时间复杂度。

优化方法

于是我发觉这是一个图，图中包含很多个环，如果一头牛进入这个环，它所得到的糖果数量一定是环的长度+入环时的糖果数。怎么记录环的长度呢？
当牛走到它曾走过的地方时，此时图就构成一个环。提前用s数组记录走到i点时获得的糖果数量，当前获得的糖果数now-上一次来到的糖果数s[i]就是环的长度，用h数组记录。
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
int n,nxt[mx];
int s[mx],h[mx];
bool vis[mx];
int flag;
int find(int i,int now){
	if(h[i]!=0) return now-1+h[i]; // 如果在环上直接返回环的长度 
	if(vis[i]){
		h[i]=now-s[i]; // 记录环的长度 
		flag=i; // 标记 
		return now-1;
	} 
	s[i]=now;
	vis[i]=true;
	int ans=find(nxt[i],now+1);
	if(flag!=0){
		if(i==flag) flag=0;
		else h[i]=h[flag];
	}
	else h[i]=h[nxt[i]]+1;
	vis[i]=false;
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>nxt[i];
	for(int i=1;i<=n;i++){
		cout<<find(i,1)<<endl;
	} 
}

并查集方法

牛只有两种可能，在环上，和在环的路上。可以分开讨论。

  1. 如果在环上，那么答案就是环的长度。
  2. 如果在去环的路上，答案就是环的长度+去环路的长度
    通过并查集，我们可以统计出所有环的长度，去环路的长度可以另外计数
    代码如下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include<bits/stdc++.h>
    using namespace std;
    const int mx=1e5+10;
    int n,nxt[mx],fa[mx],ans[mx];

    int findF(int x){ // 并查集找祖先 
    	if(fa[x]==x) return x;
    	return fa[x]=findF(fa[x]);
    }
    void merge(int x,int y){ // 并查集合并 
    	fa[findF(x)]=findF(y);
    }
    void findCircle(int x,int y){ // 找环 
    	if(findF(x)==findF(y)){
    		int cnt=1;
    		for(int i=x;i!=y;i=fa[i]) cnt++;
    		for(int i=x;i!=y;i=fa[i]) ans[i]=cnt;
    		ans[y]=cnt;
    		return;
    	}
    	merge(x,y);
    	return;
    }
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++) fa[i]=i;
    	for(int i=1;i<=n;i++){
    		cin>>nxt[i];
    		findCircle(nxt[i],i);
    	}
    	for(int i=1;i<=n;i++){
    		if(!ans[i]){ // 如果不在环上，统计去环的长度 
    			int cnt=1,j;
    			for(j=i;!ans[j];j=fa[j]) cnt++;
    			ans[i]=cnt+ans[j]; // 加上环的长度 
    		}
    		cout<<ans[i]<<endl;
    	}
    }

于是就解决了一道绿题
关键是对于环的统计
首篇学习记录