정보 전달, 낙 곡 의 향상 경험 지, 그림 의 옮 겨 다 니 기
그림 은 매우 중요 한 데이터 구조 로 대상 의 복잡 한 연습 을 묘사 하 는 것 이다.여기 서 접촉 도의 기본 개념 을 시작한다.
그림 을 잘 파악 하면 경기 에서 대부분의 점 수 를 얻 을 수 있다.
본론
제1 문제: 정보 전달
이 문 제 는 비교적 쉬 워 서 두 가지 방법 이 있 는데 하 나 는 집 을 함께 찾 는 것 이 고 하 나 는 깊이 찾 는 것 이다.
개인 적 으로 집회 가 빠르다 고 생각 하고...
물론 폭력 검색 도 무시 할 수 없다. 본 문 제 는 가장 작은 고 리 를 구 하 는 과정 으로 바 뀌 었 다. 그 다음 에 각 점 에 들 어가 서 한 번 검색 할 수 있다. 만약 에 이미 한 번 훑 어 보 았 다 면 상관 하지 않 고 기 존 에 기 록 된 답 을 직접 출력 할 수 있다. 그렇지 않 으 면 dfs 로 한 번 직접 현재 시간 표를 최초 로 업데이트 하 는 것 이 언제 인지 살 펴 보 자.
기록 하면 돼.
병합 방법
맞습니다. 바로 집합 입 니 다. 우 리 는 f 로 그의 아버 지 를 표시 합 니 다. d 는 현재 점 에서 조상 까지 의 포인트 (자신 포함, 조상 포함 하지 않 음) 를 표시 합 니 다. 만약 에 현재 나의 목표 점 이 나 와 연결 되 어 있다 면 d [t] + d [i] + 1 로 min 을 업데이트 할 수 있 습 니 다.왜?만약 에 t, i 가 원래 연결 되 어 있 었 다 면 지금 은 한 변 을 더 연결 하면 하나의 고리 가 되 는 것 과 같 고 이 고리 의 포 인 트 는 d [t] + d [i] + 1 (조상) 이다.그럼, father 를 기록 하면 됩 니 다.
#include
#include
#include
int f[200010],d[200010];
int n;
int fx,fy;
int min=2147483647;
int findpa(int x)
{
if(f[x]!=x)
{
int last=f[x];
f[x]=findpa(f[x]);
d[x]+=d[last];
}
return f[x];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
fx=findpa(i),fy=findpa(t);
if(fx!=fy) {d[i]=d[t]+1;f[fx]=fy;}
else if(d[i]+d[t]+1 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
