题目描述
A 国有 n 座城市,编号从 1 到 n ,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入描述:
第一行有两个用一个空格隔开的整数 n,m ,表示 A 国有 n 座城市和 m 条道路。接下来 m 行每行 3 个整数 x, y, z ,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y ,两座城市之间可能有多条道路 。接下来一行有一个整数 q,表示有 q 辆货车需要运货。接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 。
输出描述:
共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出 -1 。
示例1
输入
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出
3
-1
3
备注
对于 30% 的数据, 0 < n < 1,000,0 < m < 10,000,0 < q< 1,000 ;
对于 60% 的数据, 0 < n < 1,000,0 < m < 50,000,0 < q< 1,000 ;
对于 100% 的数据, 0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,000 。
解答
第一眼望去,最暴力的方法就是用Floyd对每次输入的2个点作最大生成树的操作,输出路径中的最小值。很显然,这一定会超时的。
进一步思考,我们发现有一些权值较小的边是不会被走过的。正如样例中的第三条边,就算还有另外无数条边,这条边也不会被经过。我们可以删去这些这样的边。由此类推,我们可以发现,所有可能被经过的边一定就在这张图的最大生成树上,我们只要跑一遍最大生成树,无用边就可删除。
继续思考,在得到这样一棵树后,要求任意2个点之间的边权最小值最大,且路径唯一,那么很容易想到lca算法。
我们用 表示点向上步到达的结点; 表示点向上 步的路径中的边权最小值。
就有如下方程:
进一步思考,我们发现有一些权值较小的边是不会被走过的。正如样例中的第三条边,就算还有另外无数条边,这条边也不会被经过。我们可以删去这些这样的边。由此类推,我们可以发现,所有可能被经过的边一定就在这张图的最大生成树上,我们只要跑一遍最大生成树,无用边就可删除。
继续思考,在得到这样一棵树后,要求任意2个点之间的边权最小值最大,且路径唯一,那么很容易想到lca算法。
我们用 表示点向上步到达的结点; 表示点向上 步的路径中的边权最小值。
就有如下方程:
对于每次输入的只要在跑时,累加权值最后输出就行了。
如果不在一棵树上,输出。
题目得到完美解决。。。
代码:
#include <bits/stdc++.h> using namespace std; const int N=1000000,M=1000010; int f[N]={},ver[M],edge[M],Next[M],head[M]; int n,m,tot=0,root=0; int fa[26][N]={},dep[N],dep1[N]; struct ACF{ int x,y,z; }a[N]={}; int ans1=1e9; int e[N]={},w[100][N]={}; inline int getf(int x) { if (f[x]==x) return x; return f[x]=getf(f[x]); } bool cmp(ACF p,ACF o) { return p.z>o.z; } void insert(int x,int y,double z) { ver[++tot]=y;//终点 edge[tot]=z;//权值 Next[tot]=head[x]; head[x]=tot; } void kruskal() { for (int i=1;i<=m;i++) { int x=getf(a[i].x),y=getf(a[i].y); if (x!=y) { f[x]=y; insert(a[i].x,a[i].y,a[i].z); insert(a[i].y,a[i].x,a[i].z); e[x]=y; } } } bool vis[N]={}; void dfs(int x,int y) { if (vis[x]) return; vis[x]=1; dep[x]=y; for (int i=head[x];i;i=Next[i]) { int l=ver[i]; if (l==fa[0][x]) continue; fa[0][l]=x; w[0][l]=edge[i]; dfs(l,y+1); } } void init() { // fa[0][root]=-1; // dfs(root,0); for (int i=1;i<=n;i++) if (!vis[i]){ dep[i]=1; dfs(i,1); fa[0][i]=i; w[0][i]=10000000; } for (int i=1;(1<<i)<n;i++) for (int j=1;j<=n;j++) if (fa[i-1][j]<0) fa[i][j]=-1,w[i][j]=1e9; else fa[i][j]=fa[i-1][fa[i-1][j]],w[i][j]=min(w[i-1][j],w[i-1][fa[i-1][j]]); } inline int lca(int u,int v) { ans1=1e9; if (getf(u)!=getf(v)) return -1; if (dep[u]>dep[v]) swap(u,v); // for (int i=0,d=dep[v]-dep[u];d;i++,d>>=1) // if (d&1) v=fa[i][v],ans1=min(ans1,w[i][v]); for (int i=20;i>=0;i--) if (dep[fa[i][v]]>=dep[u]) ans1=min(ans1,w[i][v]),v=fa[i][v]; if (u==v) return ans1; for (int i=25;i>=0;i--) if (fa[i][v]!=fa[i][u]) { ans1=min(ans1,min(w[i][u], w[i][v])); v=fa[i][v]; u=fa[i][u]; } ans1=min(ans1,min(w[0][u], w[0][v])); return ans1; } int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); for (int i=1;i<=n;i++) f[i]=i; sort(a+1,a+m+1,cmp); kruskal(); for (int i=1;i<=n;i++) if (!e[i]) {root=i;break;} init(); int q; scanf("%d",&q); for (int i=1;i<=q;i++) { int kk,ll; ans1=1e9; scanf("%d%d",&kk,&ll); ans1=lca(kk,ll); printf("%d\n",ans1); } return 0; }
来源:魃魈魁鬾魑魅魍魉