3287 货车运输 2013年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
传送门
题目描述 Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入描述 Input Description
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出描述 Output Description
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
样例输入 Sample Input
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
样例输出 Sample Output
3
-1
3
数据范围及提示 Data Size & Hint
对于 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。
分类标签 Tags
最小生成树 图论 大陆地区 NOIP全国联赛提高组 2013年
/*
spfa暴力.
30.
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 10001
#define MAXM 100001
using namespace std;
int head[MAXN],dis[MAXN],n,m,cut,k;
struct data{int v,next,x;}e[MAXM];
bool b[MAXN];
queue<int>q;
void add(int u,int v,int z)
{
e[++cut].v=v;
e[cut].x=z;
e[cut].next=head[u];
head[u]=cut;
}
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;if(ch==EOF) return -1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void spfa(int s)
{
memset(dis,0,sizeof dis);
dis[s]=1e9;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();b[u]=false;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]<min(dis[u],e[i].x)) {
dis[v]=min(dis[u],e[i].x);
if(!b[v]) b[v]=true,q.push(v);
}
}
}
}
int main()
{
int x,y,z;
n=read(),m=read();
while(m--)
{
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
k=read();
while(k--)
{
x=read(),y=read();
spfa(x);
if(!dis[y]) printf("-1\n");
else printf("%d\n",dis[y]);
}
return 0;
}/*
最大生成树+带权LCA+并查集.
好题.
每次询问任意两点之间边权最大路径的最小值.
▲读入的时候不能建边.
先kruskal建一棵树并保存数的形态.(prim只能求权值无法保存形态).
搞的时候维护一个dis[i][j]数组表示从i号节点向上2^j层的到i的最小值.
然后LCA的时候步步取小,步步取小,步步取小.
若deep[i]==0&&i!=1 即改点没有遍历到,return -1.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 50001
#define D 16
using namespace std;
int head[MAXN],n,m,cut,tot,father[MAXN],fa[MAXN][D+5],deep[MAXN],dis[MAXN][D+5];
struct edge
{
int v;
int next;
int x;
}
e[MAXN<<1];
struct data
{
int x,y,z;
}
s[MAXN];
void add(int u,int v,int z)
{
tot++;
e[tot].x=z;
e[tot].v=v;
e[tot].next=head[u];
head[u]=tot;
}
int ffind(int x)
{
if(x!=father[x]) return father[x]=ffind(father[x]);
return x;
}
bool cmp(const data &x,const data &y)
{
return x.z>y.z;
}
void dfs(int u,int x)
{
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(!deep[v]&&v!=1)
{
deep[v]=deep[u]+1;
fa[v][0]=u;
dis[v][0]=e[i].x;//dis处理.
dfs(v,x+1);
}
}
}
void get_father()
{
for(int j=1;j<=D;j++)
for(int i=1;i<=n;i++)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
dis[i][j]=min(dis[i][j-1],dis[fa[i][j-1]][j-1]);
}
}
int get_same(int u,int v)
{
for(int i=0;i<=D;i++)
if((1<<i)&v)
{
tot=min(tot,dis[u][i]);
u=fa[u][i];
}
return u;
}
int lca(int u,int v)
{
if((u!=1&&!deep[u])||(v!=1&&!deep[v])) return -1;
tot=1e9;
if(deep[u]<deep[v]) swap(u,v);
u=get_same(u,deep[u]-deep[v]);
if(u==v) return tot;
for(int i=D;i>=0;i--)
{
if(fa[u][i]!=fa[v][i])
{
tot=min(tot,dis[u][i]);
tot=min(tot,dis[v][i]);
u=fa[u][i];
v=fa[v][i];
}
}
tot=min(tot,min(dis[u][0],dis[v][0]));
return tot;
}
int main()
{
memset(head,-1,sizeof(head));
memset(dis,127/3,sizeof(dis));
int x,y,z,u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
//add(x,y,z);
s[i].x=x;s[i].y=y;s[i].z=z;
}
sort(s+1,s+m+1,cmp);
for(int i=1;i<=m;i++)
{
u=s[i].x,v=s[i].y;
int r1=ffind(u),r2=ffind(v);
if(r1!=r2)
{
add(u,v,s[i].z);
add(v,u,s[i].z);
father[r2]=r1;
cut++;
if(cut==n-1) break;
}
}
dfs(1,0);
get_father();
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
return 0;
}