题目描述
A 国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
数据范围
对于30%的数据，$ 0 < n < 1000，0 < m < 10000，0 < q< 1,000 $
对于60%的数据，$ 0 < n < 1000，0 < m < 50000，0 < q< 1,000 $
对于100%的数据，$ 0 < n < 10000，0 < m < 50000，0 < q < 30000，0 ≤ z ≤ 100,000 $
解题报告
这一题一看，发现很难。
(但是其实不难
冷静分析，发现我们可以用一个FLOYD的思想来写，但是这样只有30pts
好像还要优化…
100pts做法
我们其实只需要这个图的最大生成树即可，然后如果两个点联通，则它们连接的边就是答案，用倍增搞一下就行。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include <algorithm> #include <iostream> #include <climits> #include <cstring> #include <cstdio> const int MAXN = 10000 + 5; const int MAXM = 50000 + 5; struct Tree{ //存储最大生成树 int to,next,w; }t[MAXM]; struct Side{ //存储图（KrusKal不需要存整个图，只需要存边即可） int u,v,w; bool operator < (const Side &x) const{ //最大生成树的排序 return w > x.w; } }e[MAXM]; int N,M,log2N; int head[MAXN],cnt; int fa[MAXN],deep[MAXN]; bool check[MAXN]; int f[MAXN][20 + 5],w[MAXN][20 + 5]; //w[i][j]表示第i个点到向上第2^j个点的路程之间的最大权值 inline void addTree(int u,int v,int w){ t[++cnt] = Tree{v,head[u],w}; head[u] = cnt; t[++cnt] = Tree{u,head[v],w}; head[v] = cnt; } inline void init(){ for(int i = 1;i <= N;i++) fa[i] = i; } int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); } void Union(int x,int y){ fa[find(x)] = find(y); } void KrusKal(){ init(); std::sort(e + 1,e + M + 1); int cnt = 0; for(int i = 1;i <= M;i++){ if(find(e[i].u) != find(e[i].v)){ Union(e[i].u,e[i].v); addTree(e[i].u,e[i].v,e[i].w); cnt++; } if(cnt == N - 1) break; } } void dfs(int v,int fa,int d){ //预处理每一个点 check[v] = true; f[v][0] = fa; deep[v] = d; for(int i = head[v];i;i = t[i].next){ if(!check[t[i].to]){ w[t[i].to][0] = t[i].w; dfs(t[i].to,v,d + 1); } } } void ycl(){ //预处理LCA for(int i = 1;i <= N;i++) if(!check[i]) dfs(i,0,1); for(int j = 1;j <= 20;j++){ for(int i = 1;i <= N;i++){ f[i][j] = f[f[i][j-1]][j-1]; w[i][j] = std::min(w[i][j-1],w[f[i][j-1]][j-1]); } } } int lca(int x,int y){ //查询 if(deep[x] < deep[y]) std::swap(x,y); int ret = INT_MAX; for(int i = 20;i >= 0;i--){ if(deep[f[x][i]] >= deep[y]){ ret = std::min(ret,w[x][i]); x = f[x][i]; } } if(x == y) return ret; for(int i = 20;i >= 0;i--){ if(f[x][i] != f[y][i]){ ret = std::min(ret,std::min(w[x][i],w[y][i])); x = f[x][i]; y = f[y][i]; } } return ret = std::min(ret,std::min(w[x][0],w[y][0])); } void query(){ int q; scanf("%d",&q); while(q--){ int x,y; scanf("%d%d",&x,&y); if(find(x) != find(y)) printf("-1\n"); else printf("%d\n",lca(x,y)); } } int main(){ scanf("%d%d",&N,&M); for(int i = 1;i <= M;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); KrusKal(); ycl(); query(); return 0; } |
发表评论