正文
NOIP2013 货车运输
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
3 ．货车运输
(truck.cpp/c/pas)
【问题描述】
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。
【输入输出样例】
|
truck.in |
truck.out |
||||
|
4 |
3 |
3 |
|||
|
1 |
2 |
4 |
-1 |
||
|
2 |
3 |
3 |
3 |
||
|
3 |
1 |
1 |
|||
|
3 |
|||||
|
1 |
3 |
||||
|
1 |
4 |
||||
|
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。
【思路】
MST+LCA
可以知道如果运最大重量的货物，货车所走的一定是最大生成树上的边。
方法：kruskal求解最大生成树。
对于每个询问uv，找到两者的最近公共祖先r，那么货车走过的路线就是u->r->v，所以只需要在寻找LCA的时候比较路上的最小边即可。
方法：暴力。先将uv挪到相同深度上来，然后并行向上寻找公共祖先。
注意：当uv不属于同一个树中的时候意味着两者不互通，需要提前判断。
【代码】
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<(c);a++)
using namespace std; const int maxn = +, maxm=+;
int n,m;
int father[maxn]; //并查集
struct Edge{
int u,v,d;
bool operator <(const Edge& rhs) const{ //最大生成树
return d>rhs.d;
}
};
struct Edge2{
int v,d,next;
};
inline int find(int u) {
return u==father[u]? u:father[u]=find(father[u]);
}
struct LCA{
int first[maxm]; //链表式存初图
Edge2 e[maxm]; int en; int dist[maxn][maxn]; //[][]
int d[maxn]; //深度数组
int p[maxn]; //p数组记录父节点
int root; void init() {
en=; root=n/; //root的选取会影响时间
for(int i=;i<n;i++) first[i]=-;
d[]=;
}
void AddEdge(int u,int v,int d){
++en;
e[en].v=v; e[en].d=d;
e[en].next=first[u];
first[u]=en;
}
void build_tree(int u,int fa) { //have failed
//根据MST得出的初图(edges)建树->depth[] parent[] dist[][]
//无根树->有根树
for(int i=first[u];i>;i=e[i].next) { //i=next[i]!!!
int v=e[i].v;
if(v!=fa) {
d[v]=d[u]+; dist[u][v]=dist[v][u]=e[i].d;
build_tree(v,p[v]=u); //v!=fa
}
}
}
void Move(int& u,int depth,int &ans){ //u溯回到高度为depth的祖先的位置
while(d[u]!=depth) { ans=min(ans,dist[u][p[u]]); u=p[u]; }
}
int query(int u,int v) {
if(find(u) != find(v)) return -; //uv之间不可达
int ans=<<;
if(d[u]<d[v]) Move(v,d[u],ans); else if(d[u]>d[v]) Move(u,d[v],ans);
while(u != v) {
ans=min( ans , min(dist[u][p[u]],dist[v][p[v]]) );
u=p[u]; v=p[v];
}
return ans;
}
};
LCA lca;
struct Kruskal{
vector<Edge> edges; void init() {
edges.clear();
for(int i=;i<n;i++) father[i]=i;
}
void AddEdge(int u,int v,int d) {
edges.push_back((Edge){u,v,d});
}
void MST() {
lca.init();
sort(edges.begin(),edges.end());
int cnt=;
int nc=edges.size();
for(int i=;i<nc;i++) {
int u=edges[i].u,v=edges[i].v,d=edges[i].d;
int x=find(u),y=find(v);
if(x!=y) {
lca.AddEdge(u,v,d); //利用MST中的边构造lca
lca.AddEdge(v,u,d); //反向边
father[x]=y;
if(++cnt==n-) return ; //判断有n-1条边提前结束
}
}
}
}; Kruskal krus; int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
krus.init();
FOR(i,,m) { //uv 0..
int u,v,d;
cin>>u>>v>>d; u--; v--;
krus.AddEdge(u,v,d);
}
krus.MST();
lca.build_tree(lca.root,-);
int q; cin>>q;
FOR(i,,q) {
int u,v; cin>>u>>v; u--; v--;
cout<<lca.query(u,v)<<"\n";
}
return ;
}
