首页 > 代码库 > CODEVS3287货车运输 noip2013day1T3(最大生成树+倍增)
CODEVS3287货车运输 noip2013day1T3(最大生成树+倍增)
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。
思路:这道题困扰了我好久,半个月吧,最开始,和组里的人一起写了一个60分的程序,大概就是将边读入,排降序,然后每读入两个询问点,就从大边到小边进行并查集(要求边的两端点不在同一集合内),直到询问点在同一集合内,就输出,或者是-1。这种朴素的算法竟然的了60分,也是醉了。
今天,用了两三个小时研究了一下倍增(突然发现这种算法虽然可能不是很快,但是很好懂),写下了这个ACcode。其实就是最大生成树中的最小边,但是这条最小边怎么快速的在多组数据中求出呢?先读入所有的边,然后排降序,之后对于两端点不在同一集合内的边用next数组进行保存,同时将这些端点并查集。之后读入询问点,首先判断两个点是否在同一集合中,若不在就输出-1;否则就要进行——算了。。。
首先,理解一下倍增(求最近公共祖先(LCA)的美丽的算法):
三个数组:一个是深度dep[i]为i结点的深度,一个是父节点f[i][j]为i结点的2^j的祖先节点(从i向上数的),一个是距离g[i][j]为i结点到它的2^j的祖先节点的路径上的最小边。
两个算式:一个是f数组的更新:f[i][j]=f[f[i][j-1]][j-1];一个是g数组的更新:g[i][j]=min(g[i][j-1],g[f[i][j-1][j-1])(其实很好懂,因为i结点的2^j的祖先节点就是i的2^(j-1)的祖先节点的2^(j-1)的祖先节点)。
两个过程:先将两个要求最近公共祖先的点调整到同一高度(简单来说,就是将深度大的结点不断的找它的祖先节点,并不断的更新当前的最小值);然后就是当两个结点的2^j的祖先节点不是同一个的时候进行向上走,不断更新最小值,并将两个结点分别指向不同但是深度相同的祖先节点。
注意:1)找公共祖先的时候,我们默认x的深度比y的深度小,所以要先判断交换,注意这里一定是深度,第一遍的时候写成了x、y,结果。。。wa了18个点;
2)将x、y调整到同一高度后,如果二者已经相等了就可以返回最小值了;
3)对于j的取值,大概就是以2为底的n的对数;
4)深搜的时候,要对这一个节点的祖先节点进行情况的更新,然后对和它有关的每一条边的终点都进行深搜;
code:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct use{
int xx,yy,va;
}r[50001];
int next[100001]={0},point[10001]={0},en[100001]={0},fa[10001]={0},f[10001][15]={0},
g[10001][15]={0},dep[10001]={0},val[100001]={0};
int my_comp(const use &x,const use &y)
{
if (x.va>y.va) return 1;
else return 0;
}
int rool(int x)
{
if (fa[x]!=x) fa[x]=rool(fa[x]);
return fa[x];
}
void dfs(int x,int i)
{
int j,y;
dep[x]=i;
for (j=1;j<=13;++j)
{
f[x][j]=f[f[x][j-1]][j-1];
g[x][j]=min(g[f[x][j-1]][j-1],g[x][j-1]);
}
y=point[x];
while (y!=0)
{
if (dep[en[y]]==0)
{
f[en[y]][0]=x;
g[en[y]][0]=val[y];
dfs(en[y],i+1);
}
y=next[y];
}
}
int work(int x,int y)
{
int i,j,t,ans;
if (dep[x]>dep[y])
{
t=x;x=y;y=t;
}
ans=2100000000;
for (i=13;i>=0;--i)
{
if (dep[x]<=dep[f[y][i]])
{
ans=min(ans,g[y][i]);
y=f[y][i];
}
}
if (x==y) return ans;
for (i=13;i>=0;--i)
if (f[x][i]!=f[y][i])
{
ans=min(ans,min(g[x][i],g[y][i]));
x=f[x][i];y=f[y][i];
}
ans=min(ans,min(g[x][0],g[y][0]));
return ans;
}
int main()
{
int r1,r2,n,m,q,i,j,x,y,tot=0;
cin>>n>>m;
for (i=1;i<=m;++i)
scanf("%d%d%d",&r[i].xx,&r[i].yy,&r[i].va);
sort(r+1,r+m+1,my_comp);
for (i=1;i<=n;++i)
{
fa[i]=i;
}
for (i=1;i<=m;++i)
{
r1=rool(r[i].xx);
r2=rool(r[i].yy);
if (r1!=r2)
{
++tot;
next[tot]=point[r[i].xx];
point[r[i].xx]=tot;
en[tot]=r[i].yy;
val[tot]=r[i].va;
++tot;
next[tot]=point[r[i].yy];
point[r[i].yy]=tot;
en[tot]=r[i].xx;
val[tot]=r[i].va;
fa[r1]=r2;
}
}
for (i=1;i<=n;++i)
if (dep[i]==0)
dfs(i,1);
cin>>q;
for (i=1;i<=q;++i)
{
scanf("%d%d",&x,&y);
if (rool(x)!=rool(y))
printf("%d\n",-1);
else printf("%d\n",work(x,y));
}
}
CODEVS3287货车运输 noip2013day1T3(最大生成树+倍增)