hdu2874
1754 단어 데이터 구조regional&&multi
분석:
LCA, 저 는 Tarjan 오프라인 을 사용 합 니 다. 모 르 는 것 은 lrj 의 검 은 책 을 볼 수 있 습 니 다.
나무 얘 기 하 는 부분 에서 얘 기 했 어 요.
예전 에 이 문 제 를 쓴 적 이 있 습 니 다.
2013-06-14
*/
#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=10005;
const int M=20005;
const int N_Q=2000005;
int n,m,q,dis[N],vis[N],father[N],ans[N_Q/2];
struct Edge{
int v,len,next;
}edge[M];
int tot,head[N];
void add(int a,int b,int c){
edge[tot].v=b;edge[tot].len=c;edge[tot].next=head[a];head[a]=tot++;
edge[tot].v=a;edge[tot].len=c;edge[tot].next=head[b];head[b]=tot++;
}
struct Ques{
int v,index,next;
}Q[N_Q];
int q_tot,q_head[N];
void add_ques(int a,int b,int index){
Q[q_tot].v=b;Q[q_tot].index=index;Q[q_tot].next=q_head[a];q_head[a]=q_tot++;
Q[q_tot].v=a;Q[q_tot].index=index;Q[q_tot].next=q_head[b];q_head[b]=q_tot++;
}
int find(int k)
{
if(father[k]==k) return k;
father[k]=find(father[k]);
return father[k];
}
void Tarjan_LCA(int k,int deep,int root)
{
int j,v;
father[k]=k;
vis[k]=root;
dis[k]=deep;
for(j=head[k];j!=-1;j=edge[j].next)
{
v=edge[j].v;
if(vis[v]!=-1) continue;
Tarjan_LCA(v,deep+edge[j].len,root);
father[v]=k;
}
for(j=q_head[k];j!=-1;j=Q[j].next)
{
v=Q[j].v;
if(vis[v]!=root) continue;
ans[Q[j].index]=dis[v]+dis[k]-2*dis[find(v)];
}
}
int main()
{
int i;
int a,b,c;
while(scanf("%d%d%d",&n,&m,&q)!=-1)
{
tot=q_tot=0;
memset(head,-1,sizeof(head));
memset(q_head,-1,sizeof(q_head));
while(m--) {scanf("%d%d%d",&a,&b,&c);add(a,b,c);}
for(i=0;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.