BZOJ 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解
代码

Description

每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果．农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖果．第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．

Input

第1行输入N，之后一行一个整数表示牛棚i的后继牛棚Xi，共N行．

Output

共N行，一行一个整数表示一只奶牛可以采集的糖果数量．

Sample Input

4
1
3
2
3
INPUT DETAILS:
Four stalls.
* Stall 1 directs the cow back to stall 1.
* Stall 2 directs the cow to stall 3
* Stall 3 directs the cow to stall 2
* Stall 4 directs the cow to stall 3

Sample Output

1
2
2
3

HINT

Cow 1: Start at 1, next is 1. Total stalls visited: 1. Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.

题解

听说这道题有环！那就来Tarjan吧、
好吧，我猜直接裸DFS也就行、、【我口胡的、

代码

#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=100010;
int nume;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int a,int b){
        v=a;nxt=b;
    }
};
int head[Maxn];
int nhead[Maxn];
Edge e[Maxn*2];
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
}
inline void reEdge(int u,int v){
    e[++nume]=Edge(v,nhead[u]);
    nhead[u]=nume;
}
int val[Maxn],ans[Maxn];
int vis[Maxn],dfn[Maxn],low[Maxn];
int bel[Maxn];
bool inque[Maxn];
int stack[Maxn];
int sVal[Maxn];
int top;
int scc;
int ind;
inline int remin(int a,int b){
    if (a<b) return a;
    return b;
}
void tarjan(int x){
    vis[x]=true;
    low[x]=dfn[x]=++ind;
    stack[++top]=x;
    inque[x]=true;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (!vis[v]){
            tarjan(v);
            low[x]=remin(low[x],low[v]);
        }else if (inque[v]){
            low[x]=remin(low[x],dfn[v]);
        }
    }
    if (dfn[x]==low[x]){
        scc++;
        int now=0;
        //printf("Scc %d\n",scc);
        while(now!=x){
            now=stack[top--];
            //printf("%d\n",now);
            bel[now]=scc;
            sVal[scc]+=val[now];
            inque[now]=false;
        }
        //printf("\n");
    }
}
int n;
inline void rebuild(){
    nume=0;
    for (int k=1;k<=n;k++){
        for (int i=head[k];i;i=e[i].nxt){
            int v=e[i].v;
            //printf("%d -> %d\n",k,v);
            if (bel[k]!=bel[v]){
                //printf("%d => %d\n",bel[k],bel[v]);
                reEdge(bel[k],bel[v]);
            }
        }
    }
}
void getAns(int x){
    vis[x]=true;
    for (int i=nhead[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (!vis[v])getAns(v);
        sVal[x]+=sVal[v];
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        addEdge(i,x);
        val[i]=1;
    }
    for (int i=1;i<=n;i++) if (!vis[i]) tarjan(i);
    rebuild();
    memset(vis,false,sizeof(vis) );
    for (int i=1;i<=scc;i++) if (!vis[i]) getAns(i);
    for (int i=1;i<=n;i++) printf("%d\n",sVal[bel[i]]);
    return 0;
}

100

101

#include<cstdio>

#include<cstring>

using namespace std;

const int Maxn=100010;

int nume;

struct Edge{

int v,nxt;

Edge(){}

Edge(int a,int b){

v=a;nxt=b;

}

};

int head[Maxn];

int nhead[Maxn];

Edge e[Maxn*2];

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

}

inline void reEdge(int u,int v){

e[++nume]=Edge(v,nhead[u]);

nhead[u]=nume;

}

int val[Maxn],ans[Maxn];

int vis[Maxn],dfn[Maxn],low[Maxn];

int bel[Maxn];

bool inque[Maxn];

int stack[Maxn];

int sVal[Maxn];

int top;

int scc;

int ind;

inline int remin(int a,int b){

if (a<b) return a;

return b;

}

void tarjan(int x){

vis[x]=true;

low[x]=dfn[x]=++ind;

stack[++top]=x;

inque[x]=true;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (!vis[v]){

tarjan(v);

low[x]=remin(low[x],low[v]);

}else if (inque[v]){

low[x]=remin(low[x],dfn[v]);

}

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

scc++;

int now=0;

//printf("Scc %d\n",scc);

while(now!=x){

now=stack[top--];

//printf("%d\n",now);

bel[now]=scc;

sVal[scc]+=val[now];

inque[now]=false;

}

//printf("\n");

}

int n;

inline void rebuild(){

nume=0;

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

for (int i=head[k];i;i=e[i].nxt){

int v=e[i].v;

//printf("%d -> %d\n",k,v);

if (bel[k]!=bel[v]){

//printf("%d => %d\n",bel[k],bel[v]);

reEdge(bel[k],bel[v]);

}

void getAns(int x){

vis[x]=true;

for (int i=nhead[x];i;i=e[i].nxt){

int v=e[i].v;

if (!vis[v])getAns(v);

sVal[x]+=sVal[v];

}

int main(){

scanf("%d",&n);

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

int x;

scanf("%d",&x);

addEdge(i,x);

val[i]=1;

}

for (int i=1;i<=n;i++) if (!vis[i]) tarjan(i);

rebuild();

memset(vis,false,sizeof(vis) );

for (int i=1;i<=scc;i++) if (!vis[i]) getAns(i);

for (int i=1;i<=n;i++) printf("%d\n",sVal[bel[i]]);

return 0;

}

一	二	三	四	五	六	日
						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

WNJXYKの博客

喂你脚下有坑