今天做了NOIP 2013 的貨車運輸。
剛開始一看題目。
**題目描述 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。
首先想到的是并查集維護的最大生成樹。
然後對于每一次詢問，一條邊一條邊的加，直到加到某一條邊後能導緻所詢問的兩點能夠聯通；因為已經按照邊權從小到大排序過，是以現在加的邊肯定是通路裡面權值最小的邊。輸出此邊即可。
不難看出，這種方法是正确的，但是對于後40%的資料會TLE。
（後面有60分的代碼，這種做法比較好寫，适合騙分）
是以，我們隻進行一次最大生成樹，之後用倍增的方法求每次詢問的兩點的LCA 查找過程中維護道路上的最小值，最後輸出即可。複雜度為O（mlogn）的。
60分代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cstdlib>
#include<string>
#include<bitset>
#include<iomanip>
#include<deque>
#define INF 1000000000
#define fi first
#define se second
#define N 100005
#define P 1000000007
#define debug(x) cerr<<#x<<"="<<x<<endl
#define MP(x,y) make_pair(x,y)
using namespace std;
int n,m,s,ti,c;
int h[N],v[N],next[N],p=,d[N],f[N];
inline int get_num()
{
int num = ;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-') flag = true;
else num = c - '0';
while (isdigit(c = getchar()))
num = num * + c - '0';
return (flag ? - : ) * num;
}
struct re
{
int x,y,bh,qz;
} q[N];
void mem()
{
for(int i=;i<=N;i++)
{
f[i]=i;
}
}
int find(int x)
{
return f[x]==x ? x:f[x]=find(f[x]);
}
void add(int a,int b,int c)
{
p++;
q[p].x=a;
q[p].y=b;
q[p].bh=p;
q[p].qz=c;
}
bool cmp(const struct re a,const struct re b)
{
return a.qz>b.qz;
}
int main()
{
n=get_num();
m=get_num();
for(int i=;i<=m;i++)
{
int qqq,w,e;
qqq=get_num();w=get_num();e=get_num();
add(qqq,w,e);
add(w,qqq,e);
}
sort(q+,q+p+,cmp);
/*for(int i=1;i<=m*2;i++)
{
cout<<q[i].qz<<" ";
}*/
c= get_num();
for(int i=;i<=c;i++)
{
int qq,w,ans=;
bool vv=;
qq=get_num();w=get_num();
mem();
for(int j=;j<=p;j++)
{
if(find(q[j].x)!=find(q[j].y))
{
f[f[q[j].x]]=f[q[j].y];
//ans=min(ans,q[j].qz);
}
if(find(qq)==find(w))
{
printf("%d\n",q[j].qz);
vv=;
break;
}
}
if(!vv)
{
printf("-1\n");
}
}
return ;
}
滿分LCA 做法：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cstdlib>
#include<string>
#include<bitset>
#include<iomanip>
#include<deque>
#define INF 1000000000
#define fi first
#define se second
#define N 100005
#define P 1000000007
#define debug(x) cerr<<#x<<"="<<x<<endl
#define MP(x,y) make_pair(x,y)
using namespace std;
int n,m,s,ti,c;
int h[N],v[N],next[N],p=,d[N],f[N],w[N],l[N],j[N][],ww[N][],deep[N];
bool vv[N];
inline int get_num()
{
int num = ;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-') flag = true;
else num = c - '0';
while (isdigit(c = getchar()))
num = num * + c - '0';
return (flag ? - : ) * num;
}
struct re
{
int x,y,bh,qz;
} q[N];
int find(int x)
{
return f[x]==x ? x:f[x]=find(f[x]);
}
void add(int a,int b,int c)
{
p++;
v[p]=b;
w[p]=c;
next[p]=h[a];
h[a]=p;
l[p]=a;
}
void addd(int a,int b,int c)
{
p++;
q[p].x=a;
q[p].y=b;
q[p].bh=p;
q[p].qz=c;
}
bool cmp(const struct re a,const struct re b)
{
return a.qz>b.qz;
}
void dfs(int x,int s)
{
deep[x]=s;
for(int i=;(<<i)<s;i++)
{
j[x][i]=j[j[x][i-]][i-];
ww[x][i]=min(ww[x][i-],ww[j[x][i-]][i-]);
//cout<<x<<" "<<i<<" :"<<ww[x][i]<<endl;
}
int p=h[x];
while(p)
{
if(vv[v[p]])
{
p=next[p];
continue;
}
vv[v[p]]=;
j[v[p]][]=x;
ww[v[p]][]=w[p];
dfs(v[p],s+);
}
return;
}
int just_doit(int x,int y)
{
int ans=;
if(deep[y]>deep[x])
{
int tt=x;
x=y;
y=tt;
}
for(int i=;i>=;i--)
{
if(deep[x]-(<<i)>=deep[y])
{
ans=min(ans,ww[x][i]);
x=j[x][i];
}
}
if(x==y)
{
return ans;
}
for(int i=;i>=;i--)
{
if(deep[x]-(<<i)>=&&j[x][i]!=j[y][i])
{
ans=min(ans,ww[x][i]);
ans=min(ans,ww[y][i]);
x=j[x][i];
y=j[y][i];
}
}
ans=min(ans,ww[x][]);
ans=min(ans,ww[y][]);
return ans;
}
int main()
{
n=get_num();
m=get_num();
for(int i=;i<=m;i++)
{
int qqq,w,e;
qqq=get_num();w=get_num();e=get_num();
addd(qqq,w,e);
addd(w,qqq,e);
}
sort(q+,q+p+,cmp);
for(int i=;i<=n;i++) f[i]=i;
int k=;p=;
for(int i=;i<=m*2;i++)
{
int a,b;
a=q[i].x;
b=q[i].y;
if(find(a)!=find(b))
{
add(a,b,q[i].qz);
add(b,a,q[i].qz);
f[find(a)]=find(f[b]);
//cout<<a<<" "<<b<<"\n";
k++;
}
if(k==n-)
break;
}
dfs(,);
c=get_num();
//cout<<ww[][]<<" &&&\n";
for(int i=;i<=c;i++)
{
int qq,w,ans=;
qq=get_num();w=get_num();
if(find(qq)!=find(w))
{
cout<<-<<"\n";
continue;
}
ans=just_doit(qq,w);
cout<<ans<<"\n";
}
return ;
}
噫！
![noip2013day1第三題 貨車運輸LCA+并查集[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)