首页 > 代码库 > CODEVS3287货车运输 noip2013day1T3(最大生成树+倍增)

CODEVS3287货车运输 noip2013day1T3(最大生成树+倍增)

题目描述 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。

思路:这道题困扰了我好久,半个月吧,最开始,和组里的人一起写了一个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(最大生成树+倍增)