BZOJ 3732 Network，bzoj3732network
2016.1.28 紀念我BZOJ第一題
Description
給你N個點的無向圖 (1 <= N <= 15,000)，記為：1…N。
圖中有M條邊 (1 <= M <= 30,000) ，第j條邊的長度為： d_j ( 1 < = d_j < = 1,000,000,000).
現在有 K個詢問 (1 < = K < = 15,000)。
每個詢問的格式是：A B，表示詢問從A點走到B點的所有路徑中，最長的邊最小值是多少？
Input
第一行： N, M, K。
第2..M+1行: 三個正整數：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X與Y之間有一條長度為D的邊。
第M+2..M+K+1行: 每行兩個整數A B,表示詢問從A點走到B點的所有路徑中，最長的邊最小值是多少？
Output
對每個詢問，輸出最長的邊最小值是多少。
Sample Input
6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
Sample Output
5
5
5
4
4
7
4
5
HINT
1 <= N <= 15,000
1 <= M <= 30,000
1 <= d_j <= 1,000,000,000
1 <= K <= 15,000
很簡單的啦~先構造個最小生成樹呗，然後a到b的路徑上的最長邊就是答案咯~想想就明白的啦~
LCA嘛~
AC代碼：
![]()
/**************************************************************
Problem: 3732
User: cscscs
Language: C++
Result: Accepted
Time:224 ms
Memory:5036 kb
****************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxlog=15;
inline int read();
struct data
{
int a,b,c;
bool operator<(data d)const {return c<=d.c;}
}Edge[30005];
int n,m,k,father[15005];
int last[60005],to[60005],w[60005],final[15005],e,vis[15005];
int f[15005][maxlog],dist[15005][maxlog],dep[15005];
int FindFather(int x)
{
if(x==father[x]) return x;
return father[x]=FindFather(father[x]);
}
void AddEdge(int a,int b,int c)
{
w[++e]=c;to[e]=b;last[e]=final[a];final[a]=e;
w[++e]=c;to[e]=a;last[e]=final[b];final[b]=e;
}
void LCA(int x)
{
vis[x]=1;
for(int i=1;(1<<i)<=dep[x];i++)
{
int c=f[x][i-1];
f[x][i]=f[c][i-1];
dist[x][i]=max(dist[c][i-1],dist[x][i-1]);
}
for(int i=final[x];i;i=last[i])
{
if(!vis[to[i]])
{
dep[to[i]]=dep[x]+1;
f[to[i]][0]=x;
dist[to[i]][0]=w[i];
LCA(to[i]);
}
}
}
int query(int a,int b)
{
int ret=1;
if(dep[a]<dep[b]) swap(a,b);
for(int i = maxlog ; i >= 0 ; i-- ) if(dep[a]-(1<<i)>=dep[b])
{
ret=max(ret,dist[a][i]);
a=f[a][i];
}
if(a==b) return ret;
for(int i = maxlog ; i >= 0 ; i-- ) if(dep[a] > (1<<i) && f[a][i] != f[b][i])
{
ret=max(ret, max(dist[a][i], dist[b][i]) );
a=f[a][i];b=f[b][i];
}
return max(ret, max(dist[a][0], dist[b][0]) );
}
int main()
{
n=read();m=read();k=read();
for(int i=1;i<=m;i++)
{
Edge[i]={read(),read(),read()};
}
sort(Edge+1,Edge+m+1);
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++)
{
int u=FindFather(Edge[i].a),v=FindFather(Edge[i].b);
if(u!=v)
{
father[u]=v;
AddEdge(Edge[i].a,Edge[i].b,Edge[i].c);
}
}
for(int i=1;i<=n;i++) if(!vis[i]) LCA(i);
while(k--)
{
int x=read(),y=read();
printf("%d\n",query(x,y));
}
}
//----------------------------------------------------
inline 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-'0';
ch=getchar();
}
return x*f;
}
View Code
