題目描述 The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing among the N pastures also conveniently numbered 1..N. Most conveniently of al ...
題目描述
The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing among the N pastures also conveniently numbered 1..N. Most conveniently of all, cow i is grazing in pasture i.
Some pairs of pastures are connected by one of N-1 bidirectional walkways that the cows can traverse. Walkway i connects pastures A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N) and has a length of L_i (1 <= L_i <= 10,000).
The walkways are set up in such a way that between any two distinct pastures, there is exactly one path of walkways that travels between them. Thus, the walkways form a tree.
The cows are very social and wish to visit each other often. Ever in a hurry, they want you to help them schedule their visits by computing the lengths of the paths between 1 <= L_i <= 10,000 pairs of pastures (each pair given as a query p1,p2 (1 <= p1 <= N; 1 <= p2 <= N).
POINTS: 200
有N(2<=N<=1000)頭奶牛，編號為1到N，它們正在同樣編號為1到N的牧場上行走.為了方 便，我們假設編號為i的牛恰好在第i號牧場上.
有一些牧場間每兩個牧場用一條雙向道路相連，道路總共有N - 1條，奶牛可以在這些道路 上行走.第i條道路把第Ai個牧場和第Bi個牧場連了起來(1 <= A_i <= N; 1 <= B_i <= N)，而它的長度 是 1 <= L_i <= 10,000.在任意兩個牧場間，有且僅有一條由若幹道路組成的路徑相連.也就是說，所有的道路構成了一棵樹.
奶牛們十分希望經常互相見面.它們十分著急，所以希望你幫助它們計劃它們的行程，你只 需要計算出Q(1 < Q < 1000)對點之間的路徑長度•每對點以一個詢問p1,p2 (1 <= p1 <= N; 1 <= p2 <= N). 的形式給出.
輸入輸出格式
輸入格式：
-
Line 1: Two space-separated integers: N and Q
-
Lines 2..N: Line i+1 contains three space-separated integers: A_i, B_i, and L_i
- Lines N+1..N+Q: Each line contains two space-separated integers representing two distinct pastures between which the cows wish to travel: p1 and p2
輸出格式：
- Lines 1..Q: Line i contains the length of the path between the two pastures in query i.
輸入輸出樣例
輸入樣例#1：4 2 2 1 2 4 3 2 1 4 3 1 2 3 2輸出樣例#1：
2 7
說明
Query 1: The walkway between pastures 1 and 2 has length 2.
Query 2: Travel through the walkway between pastures 3 and 4, then the one between 4 and 1, and finally the one between 1 and 2, for a total length of 7.
題解：
Tarjan:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000+5; int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,num1,num2; int head1[maxn],head2[maxn],a[maxn][3],dis[maxn],father[maxn]; bool vis[maxn]; struct node { int next,to,v; }e[maxn*2],q[maxn*2]; void add1(int from,int to,int dist) { e[++num1].next=head1[from]; e[num1].to=to; e[num1].v=dist; head1[from]=num1; } void add2(int from,int to,int id) { q[++num2].next=head2[from]; q[num2].to=to; q[num2].v=id; head2[from]=num2; } int find(int x) { if(x!=father[x]) father[x]=find(father[x]); return father[x]; } void merge(int x,int y) { int r1=find(x); int r2=find(y); father[r1]=r2; } void tarjan(int x) { vis[x]=1; for(int i=head2[x];i;i=q[i].next) { int to=q[i].to,id=q[i].v; if(vis[to]) a[id][2]=find(to); } for(int i=head1[x];i;i=e[i].next) { int to=e[i].to; if(!vis[to]) { dis[to]=dis[x]+e[i].v; tarjan(to); merge(to,x); } } } int main() { n=read();m=read(); for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<n;i++) { int x,y,z; x=read();y=read();z=read(); add1(x,y,z);add1(y,x,z); } for(int i=1;i<=m;i++) { a[i][0]=read();a[i][1]=read(); add2(a[i][0],a[i][1],i); add2(a[i][1],a[i][0],i); } tarjan(1); for(int i=1;i<=m;i++) printf("%d\n",dis[a[i][0]]+dis[a[i][1]]-2*dis[a[i][2]]); return 0; }
倍增:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,q,cnt; int deep[1001],head[1001],dis[1001],fa[1001][11]; bool vis[1001]; struct data{int to,next,v;}e[2001]; void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w);} void dfs(int x) { vis[x]=1; for(int i=1;i<=9;i++) { if(deep[x]<(1<<i))break; fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x];i;i=e[i].next) { if(vis[e[i].to])continue; deep[e[i].to]=deep[x]+1; dis[e[i].to]=dis[x]+e[i].v; fa[e[i].to][0]=x; dfs(e[i].to); } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int d=deep[x]-deep[y]; for(int i=0;i<=9;i++) if((1<<i)&d)x=fa[x][i]; for(int i=9;i>=0;i--) if(fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];} if(x==y)return x; else return fa[x][0]; } int main() { scanf("%d%d",&n,&q); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); } dfs(1); for(int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",dis[x]+dis[y]-2*dis[lca(x,y)]); } return 0; }
