首页 > 代码库 > 《商务旅行》解题报告
《商务旅行》解题报告
《商务旅行》解题报告
by mps
【题目描述】
某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。
假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
【输入描述】
输入文件中的第一行有一个整数n，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。
【输出描述】
在输出文件中输出商人旅行的最短时间
【输入样例】
5
1 2
1 5
3 5
4 5
4
1
3
2
5
【输出样例】
7
【分析】
数学建模：建成一棵树，求这些点逐个的树上最短路径，算法LCA
两个点的最短路径=D(x)+D(y)-2*D(LCA(x,y))
D是根到点的最短路径
很明显，就是该点的深度
通过倍增即可求出，然后直接模拟一下就OK了
【代码】
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int MaxN=70001; 8 9 int deep[MaxN],p[MaxN][30];10 int n,q;11 12 struct list{13 int to,next;14 }e[MaxN];15 int head[MaxN],cnt=0;16 17 void addedge(int u,int v){18 cnt++;19 e[cnt].to=v;20 e[cnt].next=head[u];21 head[u]=cnt;22 }23 24 void init(){25 freopen("trip.in","r",stdin);26 freopen("trip.out","w",stdout);27 scanf("%d",&n);28 int i,u,v;29 for(i=1;i<n;i++){30 scanf("%d %d",&u,&v);31 addedge(u,v);32 addedge(v,u);33 }34 }35 36 int lca(int u,int v){37 if(deep[u]<deep[v])swap(u,v);38 int c=deep[u]-deep[v],i;39 for(i=0;i<=23;i++)40 if((1<<i)&c)41 u=p[u][i];42 for(i=23;i>=0;i--)43 if(p[u][i]!=p[v][i]){44 u=p[u][i];45 v=p[v][i];46 }47 if(u==v)return u;48 else return p[u][0]; 49 }50 51 void dfs(int u){52 int i;53 for(i=1;i<=23;i++){54 if(deep[u]<(1<<i))break;55 p[u][i]=p[p[u][i-1]][i-1];56 }57 for(i=head[u];i;i=e[i].next)58 if(!deep[e[i].to]){59 deep[e[i].to]=deep[u]+1;60 p[e[i].to][0]=u;61 dfs(e[i].to);62 }63 }64 65 void solve(){66 scanf("%d",&q);67 int i,u,v,ans=0,LCA;68 for(i=1;i<=n;i++)69 if(!deep[i]){70 p[i][0]=i;71 deep[i]=1;72 dfs(i);73 }74 scanf("%d",&u);75 for(i=2;i<=q;i++){76 scanf("%d",&v);77 LCA=lca(u,v);78 ans+=deep[u]+deep[v]-2*deep[LCA];79 u=v;80 }81 printf("%d",ans);82 }83 84 int main(){85 init();86 solve();87 return 0;88 }
《商务旅行》解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。