缩点【洛谷P2921】 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

【洛谷P2921】 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

有向图缩点，之后对于入度为零的点进行记忆化搜索。

很明显不记忆化搜索的话一定很惨，我居然还交了一遍。。。

code：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int wx=200017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int st[wx],vis[wx],f[wx];

int num,Num,n,top,tot,col;

int head[wx],h[wx],in[wx];

int dfn[wx],low[wx],belong[wx],size[wx];

struct e{

	int nxt,to;

}edge[wx*2];

void add(int from,int to){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	head[from]=num;

}

struct node{

	int nxt,to;

}e[wx*2];

void Add(int from,int to){

	e[++Num].nxt=h[from];

	e[Num].to=to;

	h[from]=Num;

}

void Tarjan(int u){

	dfn[u]=low[u]=++tot;

	st[++top]=u;

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(!dfn[v]){

			Tarjan(v);

			low[u]=min(low[u],low[v]);

		}

		else if(!belong[v]){

			low[u]=min(low[u],dfn[v]);

		}

	}

	if(dfn[u]==low[u]){

		belong[u]=++col;

		size[col]++;

		while(st[top]!=u){

			belong[st[top]]=col;

			size[col]++; top--;

		}

		top--;

	}

}

int dfs(int u,int fa){

	if(f[u])return f[u];

	f[u]=size[u];

	for(int i=h[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v==fa)continue;

		f[u]+=dfs(v,u);

	}

	return f[u];

}

int main(){

	n=read();

	for(int i=1;i<=n;i++){

		int x; x=read();

		add(i,x);

	}

	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);

	for(int u=1;u<=n;u++){

		for(int i=head[u];i;i=edge[i].nxt){

			int v=edge[i].to;

			if(belong[u]!=belong[v]){

				in[belong[v]]++;

				Add(belong[u],belong[v]);

			}

		}

	}

	for(int i=1;i<=col;i++){

		if(!in[i])dfs(i,0);

	}

	for(int i=1;i<=n;i++){

		printf("%d\n",f[belong[i]]);

	}

	return 0;

}

巴特西

缩点【洛谷P2921】 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

【洛谷P2921】 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

题目描述

最新文章

热门文章