洛谷P 3367【テンプレート】そして調査セット(祖先を探す+経路圧縮(祖先を見つけるのが早い))
P 3367【テンプレート】P 1551親戚を集めて
この親戚は同じやり方で、同じ水です.同じ楽しみ;
菜鳥生成記(11)
最近,最小生成木を死滅させるKの先頭のアルゴリズム;このアルゴリズムはセットを使用して調べます.私は道を探して集を調べる問題を探しました(そして集を調べて長い間その大名を聞いて、勉強するのがおっくうです;今仕方がなくて、集を調べることができなくて、最小の木を生成するアルゴリズムは全然分かりません)
この問題ですか.水題しかし、理解と調査集に役立ちます.
祖先を探す問題でもあることに気づいた.アルゴリズムの思想とそして集と像を調べます;私は一番下に置いた(この問題は私たちの学校OJの上の問題です)
何の楽しみもないのは水の問題であげられないので、もしあれば、もっと来てください.
また、集中に圧縮経路があることを調べます(強制格が高いと聞いています).単純に理解できるのは、集合内のすべての非祖先要素の祖先を見つけるステップを短縮することです.
ACコード(残念ながらこの暴力はダメです)
アルゴリズムは分のこまごました考えを高める
時間制限:1.0 sメモリ制限:256.0 MB
問題の説明
以前子供がいたが,彼は分を分けて考えていた.しかし、彼の考えの間には因果関係がある.彼はノートにすべての考えを記録し、矢印でこの考えの由来が前のどの考えから来たのかを描きます.このノートをめくって、あなたはきっと互いに行き来する矢印にかき混ぜられて、今彼はあなたがプログラムでこれらの考えの中で最も長い因果チェーンを計算することを望んでいます.考えを1からnまで番号付けし、考えiは考えfrom[i]に由来し、from[i]入力フォーマット
1行目の正の整数nは考えの数を表す
次にn行はfrom[1],from[2],...,from[n]の順に与えられる.
出力フォーマット
行を共にして、1つの正の整数Lは最も長い考えの因果鎖の中の考えの数を表します
サンプル入力
8
0 1 0 3 2 4 2 4
サンプル出力
3
サンプルの説明
最も長い因果連鎖は:
1-> 2-> 5 (from[5]=2,from[2]=1,from[1]=0)
1-> 2-> 7 (from[7]=2,from[2]=1,from[1]=0)
3-> 4-> 6 (from[6]=4,from[4]=3,from[3]=0)
3-> 4-> 8 (from[8]=4,from[4]=3,from[3]=0)
データ規模と約定
1< =n< =1000
ACコード
これは以前書いたものです.私は書き忘れました(私は最近読んだばかりで、読めません;気まずい!主に注釈がありません)
この親戚は同じやり方で、同じ水です.同じ楽しみ;
菜鳥生成記(11)
最近,最小生成木を死滅させるKの先頭のアルゴリズム;このアルゴリズムはセットを使用して調べます.私は道を探して集を調べる問題を探しました(そして集を調べて長い間その大名を聞いて、勉強するのがおっくうです;今仕方がなくて、集を調べることができなくて、最小の木を生成するアルゴリズムは全然分かりません)
この問題ですか.水題しかし、理解と調査集に役立ちます.
祖先を探す問題でもあることに気づいた.アルゴリズムの思想とそして集と像を調べます;私は一番下に置いた(この問題は私たちの学校OJの上の問題です)
何の楽しみもないのは水の問題であげられないので、もしあれば、もっと来てください.
また、集中に圧縮経路があることを調べます(強制格が高いと聞いています).単純に理解できるのは、集合内のすべての非祖先要素の祖先を見つけるステップを短縮することです.
ACコード(残念ながらこの暴力はダメです)
#include<bits/stdc++.h>
using namespace std;
const int N=1e+4+10;
const int M=2e+5+10;
int pre[N]={
0};
/*
4 3
1 1 2
1 3 4
1 2 3
*/
int find(int x)
{
//
int t=x;
while(pre[t]!=t)// ( )
{
t=pre[t];//
}
return t;//
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)//
{
//
pre[i]=i;
}
for(int i=1;i<=m;i++)
{
int z,x,y;
cin>>z>>x>>y;
if(z==1)//
{
// ( )
// , ,
// , ;
int t1=find(x);// x
int t2=find(y);// y
pre[y]=t1;//y x
pre[t2]=t1;//y x
}
else// x y
{
int t1=find(x);// x
int t2=find(y);// y
if(t1==t2)//
cout<<'Y'<<endl;
else//
cout<<'N'<<endl;
}
}
return 0;
}
アルゴリズムは分のこまごました考えを高める
時間制限:1.0 sメモリ制限:256.0 MB
問題の説明
以前子供がいたが,彼は分を分けて考えていた.しかし、彼の考えの間には因果関係がある.彼はノートにすべての考えを記録し、矢印でこの考えの由来が前のどの考えから来たのかを描きます.このノートをめくって、あなたはきっと互いに行き来する矢印にかき混ぜられて、今彼はあなたがプログラムでこれらの考えの中で最も長い因果チェーンを計算することを望んでいます.考えを1からnまで番号付けし、考えiは考えfrom[i]に由来し、from[i]
1行目の正の整数nは考えの数を表す
次にn行はfrom[1],from[2],...,from[n]の順に与えられる.
出力フォーマット
行を共にして、1つの正の整数Lは最も長い考えの因果鎖の中の考えの数を表します
サンプル入力
8
0 1 0 3 2 4 2 4
サンプル出力
3
サンプルの説明
最も長い因果連鎖は:
1-> 2-> 5 (from[5]=2,from[2]=1,from[1]=0)
1-> 2-> 7 (from[7]=2,from[2]=1,from[1]=0)
3-> 4-> 6 (from[6]=4,from[4]=3,from[3]=0)
3-> 4-> 8 (from[8]=4,from[4]=3,from[3]=0)
データ規模と約定
1< =n< =1000
ACコード
#include<bits/stdc++.h>
using namespace std;
const int N=1e+3+10;
int pre[N]={
0};
int find(int x)
{
//
int t=x;
int k=0;//
while(pre[t]!=t)// ( )
{
k++;
t=pre[t];//
}
return k;//
}
int main()
{
int n,max1=-1;
cin>>n;
for(int i=1;i<=n;i++)
cin>>pre[i];// i
for(int i=1;i<=n;i++)
{
int x=find(i);//
max1=max(x,max1);//
}
cout<<max1<<endl;
return 0;
}
これは以前書いたものです.私は書き忘れました(私は最近読んだばかりで、読めません;気まずい!主に注釈がありません)
#include<stdio.h>
int main()
{
// ， ( )
int n;
int a[1001];
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int k,x=1,max=1;
for(int i=n;i>=1;i--)
{
k=i,x=1;
while(a[k])
{
if(a[k]!=0)
{
x++;
k=a[k];
}
}
if(max<x)
max=x;
}
printf("%d",max);
return 0;
}