首页 > 代码库 > BZOJ——1602: [Usaco2008 Oct]牧场行走

BZOJ——1602: [Usaco2008 Oct]牧场行走

2024-09-19 22:34:05   220人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=1602

题目描述

N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

输入

*第一行：两个被空格隔开的整数：N和Q

 *第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI

*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。

输出

*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。

样例输入

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

样例输出

2
7

提示

 

来源

资格赛

 

很惨的一下午：倍增死活没过，然后改树剖就A了~~~QAQ

 

先贴个没过的请大佬找找错

技术分享
 1 #include <algorithm> 2 #include <cstdio> 3   4 using namespace std; 5   6 const int N(1000+15); 7 int n,q,x,y,z; 8 int dad[N<<1][23],deep[N<<1]; 9 int dis[N<<1];10 int sumedge,head[N<<1];11 struct Edge12 {13     int from,to,next,dis;14     Edge(int from=0,int to=0,int next=0,int dis=0) :15         from(from),to(to),next(next),dis(dis) {}16 }edge[N<<1];17  18 int add(int from,int to,int dis)19 {20     edge[++sumedge]=Edge(from,to,head[from],dis);21     return head[from]=sumedge;22 }23  24 void DFS(int x)25 {26     deep[x]=deep[dad[x][0]]+1;27     for(int i=0;dad[x][i];i++)28         dad[x][i+1]=dad[dad[x][i]][i];29     for(int i=head[x];i;i=edge[i].next)30         if(!deep[edge[i].to])31         {32             dad[edge[i].to][0]=x;33             dis[edge[i].to]=dis[x]+edge[i].dis;34             DFS(edge[i].to);35         }36 }37  38 int LCA(int x,int y)39 {40     if(deep[x]>deep[y]) swap(x,y);41     for(int i=20;i>=0;i--)42         if(deep[x]<=deep[dad[y][i]]) y=dad[y][i];43     if(x==y) return x;44     for(int i=20;i>=0;i--)45         if(deep[dad[x][i]]!=deep[dad[y][i]])46             x=dad[x][i],y=dad[y][i];47     return dad[x][0];48 }49  50 int main()51 {52     scanf("%d%d",&n,&q);53     for(int i=1;i<n;i++)54     {55         scanf("%d%d%d",&x,&y,&z);56         add(x,y,z); add(y,x,z);57     }58     DFS(1);59     for(;q;q--)60     {61         scanf("%d%d",&x,&y);62         printf("%d\n",dis[x]+dis[y]-(dis[LCA(x,y)]<<1));63     }64     return 0;65 }
倍增LCA

 

然后是树剖的~

 1 #include <algorithm> 2 #include <cstdio> 3 #include <vector> 4  5 using namespace std; 6  7 const int N(1000+15); 8 vector< pair<int,int> >vec[N]; 9 int n,q,x,y,z,dis[N];10 int dad[N],deep[N],size[N],top[N];11 12 void DFS(int x)13 {14     size[x]=1; deep[x]=deep[dad[x]]+1;15     for(int i=0;i<vec[x].size();i++)16         if(dad[x]!=vec[x][i].first)17         {18             dad[vec[x][i].first]=x;19             dis[vec[x][i].first]=dis[x]+vec[x][i].second;20             DFS(vec[x][i].first);21             size[x]+=size[vec[x][i].first];22         }23 }24 25 void DFS_(int x)26 {27     int t=0; if(!top[x]) top[x]=x;28     for(int i=0;i<vec[x].size();i++)29         if(dad[x]!=vec[x][i].first&&size[t]<size[vec[x][i].first]) t=vec[x][i].first;30     if(t) top[t]=top[x],DFS_(t);31     for(int i=0;i<vec[x].size();i++)32         if(dad[x]!=vec[x][i].first&&t!=vec[x][i].first) DFS_(vec[x][i].first);33 }34 35 int LCA(int x,int y)36 {37     while(top[x]!=top[y])38     {39         if(deep[top[x]]<deep[top[y]]) swap(x,y);40         x=dad[top[x]];41     }42     if(deep[x]>deep[y]) swap(x,y);43     return x;44 }45 46 int main()47 {48     scanf("%d%d",&n,&q);49     for(int i=1;i<n;i++)50     {51         scanf("%d%d%d",&x,&y,&z);52         vec[x].push_back(make_pair(y,z));53         vec[y].push_back(make_pair(x,z));54     }55     DFS(1); DFS_(1);56     for(;q;q--)57     {58         scanf("%d%d",&x,&y);59         printf("%d\n",dis[x]+dis[y]-dis[LCA(x,y)]*2);60     }61     return 0;62 }

 

BZOJ——1602: [Usaco2008 Oct]牧场行走


联系
我们