1519 过路费
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 大师 Master
题目描述 Description
在某个遥远的国家里，有 n个城市。编号为 1,2,3,…,n。这个国家的政府修建了m 条双向道路，每条道路连接着两个城市。政府规定从城市 S 到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为 2，B到C 长度为3，那么开车从 A经过 B到C 需要上交的过路费为 3。
佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而， 当他交的过路费越多他的心情就变得越糟糕。 作为秘书的你，需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上交多少过路费。
输入描述 Input Description
第一行是两个整数 n 和m，分别表示城市的个数以及道路的条数。
接下来 m 行，每行包含三个整数 a，b，w（1≤a，b≤n，0≤w≤10^9），表示a与b之间有一条长度为 w的道路。
接着有一行为一个整数 q，表示佳佳发出的询问个数。
再接下来 q行，每一行包含两个整数 S，T（1≤S,T≤n，S≠T）, 表示开始城市S 和目的城市T。
输出描述 Output Description
输出共q行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。
样例输入 Sample Input
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
样例输出 Sample Output
20
20
数据范围及提示 Data Size & Hint
对于 30%的数据，满足 1≤ n≤1000，1≤m≤10000，1≤q≤100；
对于 50%的数据，满足 1≤ n≤10000，1≤m≤10000，1≤q≤10000；
对于 100%的数据，满足 1≤ n≤10000，1≤m≤100000，1≤q≤10000；
分类标签 Tags
分治 最小生成树 图论
/*
Slf(spfa优化).
50弃疗了.
跑最小生成树后Slf.
有一个链的测试点卡不过去.
（不搞mst的话还是能卡过去的）.
论常数的重要性orz.
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define MAXN 100001
using namespace std;
int head[MAXN],n,m,k,cut,father[MAXN],tot,dis[MAXN],q[MAXN];
struct edge{int v,next;int x;}e[MAXN*2];
struct data{int x,y,z;}s[MAXN*2];
bool b[MAXN];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x;
}
int ffind(int x)
{
return x!=father[x]?father[x]=ffind(father[x]):x;
}
void add(int u,int v,int z)
{
e[++cut].v=v;
e[cut].x=z;
e[cut].next=head[u];
head[u]=cut;
}
bool cmp(const data &x,const data &y)
{
return x.z<y.z;
}
int spfa(int s,int t)
{
int u,v;int head1=1,tail=1;
for(int i=1;i<=n;i++) dis[i]=1e10,b[i]=false;q[head1]=s;dis[s]=0;
while(head1<=tail)
{
u=q[head1++];b[u]=false;
if(head1>n+1) head1=1;
for(int i=head[u];i;i=e[i].next)
{
v=e[i].v;
if(dis[v]>max(dis[u],e[i].x))
{
dis[v]=max(dis[u],e[i].x);
if(!b[v])
{
b[v]=true;
if(dis[v]>dis[q[head1]])
{
if(--head1<0) head1=n;
q[head1]=v;
}
else {
q[++tail]=v;
if(tail>n+1) tail=1;
}
}
}
}
}
return dis[t];
}
int main()
{
int x,y,z;
n=read(),m=read();
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++)
x=read(),y=read(),z=read(),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++)
{
x=ffind(s[i].x),y=ffind(s[i].y);
if(x!=y){
tot++;
father[x]=y;
add(s[i].x,s[i].y,s[i].z);
add(s[i].y,s[i].x,s[i].z);
}
if(tot==n-1) break;
}
k=read();
while(k--)
{
x=read(),y=read();
printf("%d
",spfa(x,y));
}
return 0;
}/*
mst定理:最小生成树里的最长边最短.
然后lca维护两点距离.
还有不要漏下某种情况.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 100001
#define D 21
using namespace std;
int head[MAXN],n,m,k,cut,father[MAXN],tot,st,fa[MAXN][D+5],deep[MAXN],dis[MAXN][D+5];
struct edge{int v,next;int x;}e[MAXN*2];
struct data{int x,y,z;}s[MAXN*2];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x;
}
int ffind(int x)
{
return x!=father[x]?father[x]=ffind(father[x]):x;
}
void add(int u,int v,int z)
{
e[++cut].v=v;
e[cut].x=z;
e[cut].next=head[u];
head[u]=cut;
}
bool cmp(const data &x,const data &y)
{
return x.z<y.z;
}
void dfs(int u,int f,int d)
{
deep[u]=d+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(f!=v){
fa[v][0]=u;
dis[v][0]=e[i].x;
dfs(v,u,d+1);
}
}
return ;
}
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]=max(dis[fa[i][j-1]][j-1],dis[i][j-1]);
return ;
}
int get_same(int u,int v)
{
for(int i=0;i<=D;i++)
{
if((1<<i)&v){
tot=max(tot,dis[u][i]);
u=fa[u][i];
}
}
return u;
}
int lca(int u,int v)
{
tot=0;
if(deep[v]>deep[u]) 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=max(tot,max(dis[u][i],dis[v][i]));
u=fa[u][i];v=fa[v][i];
}
}
tot=max(tot,max(dis[u][0],dis[v][0]));
return tot;
}
int main()
{
int x,y,z;
n=read(),m=read();
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++)
x=read(),y=read(),z=read(),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++)
{
x=ffind(s[i].x),y=ffind(s[i].y);
if(x!=y){
tot++;
father[x]=y;
add(s[i].x,s[i].y,s[i].z);
add(s[i].y,s[i].x,s[i].z);
}
if(tot==n-1) break;
}
dfs(1,1,0);
get_father();
k=read();
while(k--)
{
x=read(),y=read();
printf("%d
",lca(x,y));
}
return 0;
}