NOIP201307貨車運輸，noip201307貨車
2016.1.28
試題描述
A 國有n座城市，編號從1到n，城市之間有m條雙向道路。每一條道路對車輛都有重量限制，簡稱限重。現在有q輛貨車在運輸貨物，司機們想知道每輛車在不超過車輛限重的情況下，最多能運多重的貨物。
輸入
第一行有兩個用一個空格隔開的整數n，m，表示A國有n座城市和m條道路。接下來m行每行3個整數x、y、z，每兩個整數之間用一個空格隔開，表示從x號城市到y號城市有一條限重為z的道路。注意：x不等於y，兩座城市之間可能有多條道路。接下來一行有一個整數q，表示有q輛貨車需要運貨。接下來q行，每行兩個整數x、y，之間用一個空格隔開，表示一輛貨車需要從x城市運輸貨物到y城市，注意：x不等於y。
輸出
共有q行，每行一個整數，表示對於每一輛貨車，它的最大載重是多少。如果貨車不能到達目的地，輸出-1。
輸入示例
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
輸出示例
3
-1
3
其他說明
數據范圍：0<n<10,000，0<m<50,000，0<q<30,000，0≤z≤100,000。
先是最大生成樹構圖，注意構成的圖可能不止一棵樹，可能是好幾棵樹之間不聯通。
然後對於詢問，兩個節點不聯通（並查集判定）則無lca。
聯通的話就LCA吧，因為路徑肯定過lca，找lca的同時就把路徑上的邊權最小值更新了。
AC代碼：
![]()
#include<iostream>
#include<algorithm>
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[50005];
int n,m,q,father[10005],f[10005][20],dist[10005][20],dep[10005];
int last[100005],final[10005],to[100005],w[100005],e,vis[10005];
int FindFather(int x)
{
if(x==father[x]) return x;
return father[x]=FindFather(father[x]);
}
void AddEdge(int a,int b,int c)
{
to[++e]=b;w[e]=c;last[e]=final[a];final[a]=e;
to[++e]=a;w[e]=c;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]=min(dist[x][i-1],dist[c][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=2147483647;
if(dep[a]<dep[b]) swap(a,b);
for(int i = maxlog ; i >= 0 ; i-- ) if(dep[a]-(1<<i)>=dep[b])
{
ret=min(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 = min(ret, min(dist[a][i], dist[b][i]) );
a=f[a][i];b=f[b][i];
}
return min(ret, min(dist[a][0], dist[b][0]) );
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
Edge[i].a=read();Edge[i].b=read();Edge[i].c=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);
q=read();
while(q--)
{
int x=read(),y=read();
if(FindFather(x) != FindFather(y)) printf("-1\n");
else 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
