汕头网站建设设计公司,软件开发项目管理书籍,自己做网站可以吗,南通港闸区城乡建设局网站http://codevs.cn/problem/1519/ 时间限制: 1 s空间限制: 256000 KB题目等级 : 大师 Master题解查看运行结果题目描述 Description在某个遥远的国家里#xff0c;有 n个城市。编号为 1,2,3,…,n。这个国家的政府修建了m 条双向道路#xff0c;每条道路连接着两个城市。政府规… http://codevs.cn/problem/1519/ 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 大师 Master 题解 查看运行结果 题目描述 Description 在某个遥远的国家里有 n个城市。编号为 1,2,3,…,n。这个国家的政府修建了m 条双向道路每条道路连接着两个城市。政府规定从城市 S 到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如A到B长度为 2B到C 长度为3那么开车从 A经过 B到C 需要上交的过路费为 3。 佳佳是个做生意的人需要经常开车从任意一个城市到另外一个城市因此他需要频繁地上交过路费由于忙于做生意所以他无时间来寻找交过路费最低的行驶路线。然而 当他交的过路费越多他的心情就变得越糟糕。 作为秘书的你需要每次根据老板的起止城市提供给他从开始城市到达目的城市最少需要上交多少过路费。 输入描述 Input Description 第一行是两个整数 n 和m分别表示城市的个数以及道路的条数。 接下来 m 行每行包含三个整数 abw1≤ab≤n0≤w≤10^9表示a与b之间有一条长度为 w的道路。 接着有一行为一个整数 q表示佳佳发出的询问个数。 再接下来 q行每一行包含两个整数 ST1≤S,T≤nS≠T, 表示开始城市S 和目的城市T。 输出描述 Output Description 输出共q行每行一个整数分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。 样例输入 Sample Input 4 5 1 2 10 1 3 20 1 4 100 2 4 30 3 4 10 2 1 4 4 1 样例输出 Sample Output 20 20 数据范围及提示 Data Size Hint 对于 30%的数据满足 1≤ n≤10001≤m≤100001≤q≤100 对于 50%的数据满足 1≤ n≤100001≤m≤100001≤q≤10000 对于 100%的数据满足 1≤ n≤100001≤m≤1000001≤q≤10000 和货车运输很像 先求出最小生成树使图简化在此树上做倍增维护最大代价 1 #include algorithm2 #include cstring3 #include cstdio4 5 using namespace std;6 7 const int N(1000015);8 const int M(1000005);9 int n,m,q,u,v,ans;
10 struct Edge
11 {
12 int u,v,w;
13 }road[M];
14 bool cmp(Edge a,Edge b)
15 {
16 return a.wb.w;
17 }
18
19 int head[N],sumedge;
20 struct E
21 {
22 int v,next,w;
23 E(int v0,int next0,int w0):
24 v(v),next(next),w(w){}
25 }edge[N1];
26 void ins(int u,int v,int w)
27 {
28 edge[sumedge]E(v,head[u],w);
29 head[u]sumedge;
30 }
31
32 int fa[N];
33 int find(int x)
34 {
35 return xfa[x]?x:fa[x]find(fa[x]);
36 }
37 void K()
38 {
39 int cnt0;
40 sort(road1,roadm1,cmp);
41 for(int i1;in;i) fa[i]i;
42 for(int i1;im;i)
43 {
44 int xroad[i].u,yroad[i].v;
45 int fxfind(x),fyfind(y);
46 if(fxfy) continue;
47 fa[fx]fy;
48 ins(x,y,road[i].w);
49 ins(y,x,road[i].w);
50 if(cntn-1) return ;
51 }
52 }
53
54 int dad[N],val[N],deep[N];
55 void DFS(int x)
56 {
57 deep[x]deep[dad[x]]1;
58 for(int ihead[x];i;iedge[i].next)
59 {
60 int vedge[i].v;
61 if(dad[v]) continue;
62 val[v]edge[i].w;
63 dad[v]x; DFS(v);
64 }
65 }
66 int LCA(int x,int y)
67 {
68 int maxx0,maxn0;
69 if(deep[x]deep[y]) swap(x,y);
70 for(;deep[y]deep[x];ydad[y]) maxxmax(maxx,val[y]);
71 for(;x!y;xdad[x],ydad[y]) maxnmax(maxn,max(val[x],val[y]));
72 return max(maxn,maxx);
73 }
74
75 int main()
76 {
77 scanf(%d%d,n,m);
78 for(int i1;im;i)
79 scanf(%d%d%d,road[i].u,road[i].v,road[i].w);
80 K(); DFS(1);
81 scanf(%d,q);
82 for(;q--;)
83 {
84 scanf(%d%d,u,v);
85 printf(%d\n,LCA(u,v));
86 }
87 return 0;
88 } 转载于:https://www.cnblogs.com/Shy-key/p/7308057.html
