洛谷 P1967 NOIP2013提高组 货车运输 题解【倍增】【LCA】
点击量:218
求使图上两点间最小边权最大的题目(*////▽////*)。。。
题目描述
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。
输入输出样例
输入样例#1:
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出样例#1:
3
-1
3
说明
对于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。
解法:
floyd都不一定拿得到30分,这个题是基于贪心的。
假设图中只有一个联通块,那么任意两点间的最小边权的最大值一定是在它的最大生成树上。根据贪心我们可以知道,通过最大生成树,两点间互达,路径上的最小边权一定最大,用Kruskal算法可以形象地看出最大生成树在贪心上的作用。
我们基于最大生成树,对一个联通块任意两个点求路径上最小边权,如果用dfs,时间复杂度是$ O(NQ)$,Q是询问次数。因此,看出来最大生成树的贪心,60分是很好拿的。(不同联通块之间的查询直接输出-1即可)
有没有什么快一点的方法来求两点间路径上的信息呢?因为两点间的路径一定是最大生成树上的一条链,所以我们可以在树上做文章。我们给一棵树任取一个根,任意两点间就有了最近公共祖先。我们知道两点的路径一定经过最近公共祖先,所以我们思路就有了,我们先把图建成一棵最大生成树。
对于每个询问(u,v),分别查询u,v到lca(u,v)路径上最小边权,并继续取最小值,就是一次询问。那么LCA可以由tarjan或倍增求,如果用tarjan,那么查找lca的时间是O(N),但寻找到lca路径上的信息就会变成$ O(N^2)$,这时我们应该选取倍增求,因为倍增过程可以查询并处理路径上的信息,而求lca和路径访问的时间复杂度稳定为$ O(N\log N)$,这个题就迎刃而解了(。・∀・)ノ。
值得注意的是,倍增时开两个数组f[i][j],表示i节点的第$ 2^j$层祖先是谁,如果$ 2^j>depth(i)$,所求值就是根节点,fm[i][j]中i,j与f数组同义。当我们求lca时,用一个ans存储最小值,并持续更新。而我们最后判断,首先要跳到同层,然后让2的指数递减,相当于一个二分的过程。不过有可能直接使x和y跳到同一点,例如x,y的最近公共祖先就是x或y的情况,或者x,y到达一层后,离最近公共祖先刚好是2的整数次幂(这种情况在下面的标程中不会出现),因为判断条件是x,y最终的父亲刚好为最近公共祖先,因此还要更新一层。为防止这种情况出现,我们只要特判x是否等于y,再看需不需要加就可以了。
Code:
#include<cstdio>
#include<algorithm>
int min(int x,int y)
{
return x<y?x:y;
}
struct edge
{
int x,y,v;
edge(int x,int y,int v)
{
this->x=x;
this->y=y;
this->v=v;
}
edge(){}
friend bool operator <(edge a,edge b)
{
return a.v>b.v;//最大生成树
}
}e[51000],tree[51000];
int cnt=0;
int s[10100];
int my_find(int x)
{
if(s[x]==x)
return x;
return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
s[my_find(y)]=my_find(x);
}
struct node
{
int n,v;
node *nxt;
node(int n,int v)
{
this->n=n;
this->v=v;
nxt=NULL;
}
node()
{
nxt=NULL;
}
};
node head[10100],*tail[10100];
int f[10100][22],fm[10100][22];
int dpt[10100];
void dfs(int x)
{
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(!dpt[p->n])
{
dpt[p->n]=dpt[x]+1;
f[p->n][0]=x;
fm[p->n][0]=p->v;
dfs(p->n);
}
}
}
int main()
{
int n,m,u,v,w;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
tail[i]=&head[i];
s[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
e[i]=edge(u,v,w);
}
std::sort(e+1,e+m+1);
for(int i=1;i<=m;i++)
if(my_find(e[i].x)!=my_find(e[i].y))
{
tree[++cnt]=e[i];
my_union(e[i].x,e[i].y);
}
for(int i=1;i<=cnt;i++)
{
u=tree[i].x;
v=tree[i].y;
w=tree[i].v;
tail[u]->nxt=new node(v,w);
tail[u]=tail[u]->nxt;
tail[v]->nxt=new node(u,w);
tail[v]=tail[v]->nxt;
}
for(int i=1;i<=n;i++)
{
s[i]=my_find(i);//顺便整理状态
if(!dpt[i])
{
f[i][0]=i;
fm[i][0]=0x3fffffff;
dpt[i]=1;
dfs(i);//根
}
}
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)
{
f[j][i]=f[f[j][i-1]][i-1];
fm[j][i]=min(fm[j][i-1],fm[f[j][i-1]][i-1]);
}
int q;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&u,&v);
if(s[u]!=s[v])
{
printf("-1\n");
continue;
}
if(dpt[u]<dpt[v])
{
int t=u;
u=v;
v=t;
}
int ans=99999999;
for(int i=20;i>=0;i--)
if(dpt[u]-(1<<i)>=dpt[v])
{
ans=min(ans,fm[u][i]);
u=f[u][i];
}
for(int i=20;i>=0;i--)
if(f[u][i]!=f[v][i])
{
ans=min(ans,fm[u][i]);
ans=min(ans,fm[v][i]);
u=f[u][i];
v=f[v][i];
}
if(u!=v)
{
ans=min(ans,fm[u][0]);
ans=min(ans,fm[v][0]);
}
printf("%d\n",ans);
}
return 0;
}
… [Trackback]
[…] Find More Info here to that Topic: wjyyy.top/568.html […]
… [Trackback]
[…] Here you will find 16173 additional Information to that Topic: wjyyy.top/568.html […]