[luogu 1967] [noip 2013 货车运输] : LCA+最大生成树+并查集

题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式：

输出文件名为 truck.out。

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货

车不能到达目的地，输出-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。

一些想法

一句话题意：n个点m条边的无向带权图，求某两点之间最短路径上权值最小的那条边的权值。

货车要运尽可能多的货，就应该走有尽可能大承受力的道路，因此，货车一定在这些点的最大生成树上运货，当然，可能会有些点并不连通，所以也可能是最大生成树的森林。那么查询这两个点路径上权值最小的那条边的权值我们使用LCA，然而我并不会tarjan的LCA的离线做法，所以就用倍增吧。

首先对于输入的边权值排序，然后使用Kruskal求得最大生成树森林。这里我们用并查集维护点与点之间是否在一棵树上。对于求LCA我们使用一个Up数组，Up[i][j]表示i节点的向上跳2^j步到达的点。那么 Up[i][0]就是i节点的父节点，  并且Up[i][j]=Up[Up[i][j-1]][j-1] ，即i节点向上跳2^j等同于i节点向上跳2^j-1后再跳2^j-1，因为2^j=2^(j-1)+2^(j-1)。其次我们还需要一个数组Min，Min[i][j]表示i节点到Up[i][j] 路径上最小的边权值，那么Min[i][j]=min(Min[i][j-1],Min[Up[i][j-1]][j-1]),即i节点到Up[i][j]路径上最小边权值等于节点i到Up[i][j-1]路径上的最小边权值以及节点Up[i] [j-1]到Up[Up[i][j-1][j-1]路径上的最小边权值二者的最小值。我们需要先预处理这两个数组，然后使用倍增求答案，但是在倍增前我们必须保证两个节点在树中的深度是相同的，所以我们还需要一个数组rank记录节点在树中的深度，一遍dfs求得。然后我们对于深度不等的节点，调整较深节点，我们从大到小枚举j，如果它向上跳2^j的深度还是深于另一个节点，就跳，否则不跳，可以确定的是，最终一定会跳到同一深度，在跳的同时我们记录一下在这路径上的最小边权值，同一深度后进行同步倍增，一直到它们的祖先节点是他们的公共祖先，停止倍增，向上同时上提，同时记录在向上倍增的路径边权最小值。

简述：kruskal求最大生成树，并查集维护同一棵树，倍增求LCA得最短路径同时记录路径边权最小值。

#include
#include
#include
#include
#include
#include
using namespace std;
#define debug(x) cerr<<#x<<'='<#define M 50007
#define N 10006
#define INF (1<<31)-233struct lee{int s,t,w;
}sylvia[M];int father[N],rank[N];
int Up[N][23],Min[N][23];
int q,n,m,x,y;
int first[M],nxt[M]; 
int weight[M],terminal[M];//weight记录第i条边的边权值 terminal记录第i条边指向点
bool vis[M];
int k=0;bool cmp(lee x,lee y){return x.w>y.w;
}int Find(int x){//并查集int k,j,r;r=x;while (r!=father[r]) r=father[r];k=x;while (k!=r){j=father[x];father[x]=r;k=j;}return r;
}void Unite(int x,int y){//并查集x=Find(x);y=Find(y);if(x==y) return;else  father[x]=y;
}void Add(int x,int y,int z){//对最大生成树边的处理k++;weight[k]=z;terminal[k]=y;nxt[k]=first[x];first[x]=k;
}void Kruskal(void){//最大生成树for (int i=1;i<=m;i++){if (Find(sylvia[i].s)!=Find(sylvia[i].t)){Unite(Find(sylvia[i].s),Find(sylvia[i].t));Add(sylvia[i].s,sylvia[i].t,sylvia[i].w);Add(sylvia[i].t,sylvia[i].s,sylvia[i].w);}}
}void DFS(int u,int h){//预处理出Min[i][0]和Up[i][0]int temp;rank[u]=h;vis[u]=true;for (temp=first[u];temp!=-1;temp=nxt[temp]){if (!vis[terminal[temp]]){Up[terminal[temp]][0]=u;Min[terminal[temp]][0]=weight[temp];DFS(terminal[temp],h+1);}}
}int LCA(int x,int y){//求LCAint ans=INF;if (rank[x]<rank[y]) swap(x,y);for (int i=22;i>=0;i--){if(rank[Up[x][i]]>=rank[y]){ans=min(ans,Min[x][i]);x=Up[x][i];if (rank[x]==rank[y]) break;}}if (x==y) return ans;for (int i=22;i>=0;i--){if (Up[x][i]!=Up[y][i]){ans=min(ans,min(Min[x][i],Min[y][i]));x=Up[x][i];y=Up[y][i];}}ans=min(ans,min(Min[x][0],Min[y][0]));return ans;
}        int main (){memset(vis,false,sizeof(vis));memset(first,-1,sizeof(first));memset(Min,0x7f,sizeof(Min));memset(rank,0,sizeof(rank));memset(Up,0,sizeof(Up));cin>>n>>m;for (int i=1;i<=m;i++) scanf("%d%d%d",&sylvia[i].s,&sylvia[i].t,&sylvia[i].w);sort(sylvia+1,sylvia+m+1,cmp);//按边权值从大到小排序for (int i=0;ii;Kruskal();for (int i=1;i<=n;i++)if (!vis[i]) DFS(i,1);for (int i=1;i<=22;i++)for (int j=1;j<=n;j++){Up[j][i]=Up[Up[j][i-1]][i-1];Min[j][i]=min(Min[j][i-1],Min[Up[j][i-1]][i-1]);}//预处理Min和Upcin>>q;for (int i=1;i<=q;i++){scanf("%d%d",&x,&y);if (Find(x)!=Find(y)) {printf("-1\n");continue;}else printf("%d\n",LCA(x,y));}return 0;
}

春

春水初生

春林初盛

春风十里，不如你

Sylvia

二零一七年八月七日

转载于:https://www.cnblogs.com/jasmine-lee/p/7301106.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！