luogu P1967 货车运输

P1967 货车运输

2017-09-08

题目描述

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。

样例

INPUT

5 7
4 3 4440
3 1 22348
1 3 28368
2 4 25086
5 3 6991
4 3 10638
3 1 11106
4
4 5
1 3
5 4
2 5

OUTPUT

6991

28368

6991

先跑一边最大生成树,这样从生成树上走过去一定是最大权值,就不用跑spfa了...spfa看复杂度就不对啊....

这样就由图转换成树上操作...这样树上很好用的算法就可以用了

但是他会不连通，成为一个森林。那么可以用一个并查集来看是否在同一个树,不在-1

在一棵树-->A到lca(A,B)与B到lca(A,B)的最小值

在dfs的时候顺便把路上的最小权值加进去,fa[i][j]是从i号点跳2^j次是什么,MI[i][j]是i号点跳到fa[i][j]路径上最小的权值是多少

在找最大生成树中加进去要用的边(双向),找生成树时单向就可以.....不要问我为什么,sort模拟指针的数组,比结构体sort快

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=15000+999;
const int maxm=50000+999;
const int INT=int(1e9)+7;
int read(){
    int an=0,f=1;
    char ch=getchar();
    while(!('0'<=ch&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}
    return an*f;
}
int fath[maxn],cnt1;
int deep[maxn],MI[maxn][25],cnt,fa[maxn][25];
int f[maxn],pt[maxm],n,m,Q;
bool vis[maxn];
struct saber{
int nex,to,wi;
}b[maxm];
struct data{
int from,to,wi;
}e[maxm];
void fadd(int x,int y,int z){
    cnt1++;
    e[cnt1].wi=z;
    e[cnt1].from=x;
    e[cnt1].to=y;
}
void F(){
    for(int i=1;i<=n;i++)fath[i]=i;
    for(int i=1;i<=m;i++)pt[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=20;j++)MI[i][j]=INT;
}//pt是指针,fa>father 
bool cmp(int x,int y){
    return e[x].wi>e[y].wi;
}//按照wi排序的指针 
int found(int x){
    if(fath[x]!=x)fath[x]=found(fath[x]);
    return fath[x];
}
void add(int x,int y,int z){
    cnt++;
    b[cnt].nex=f[x];
    b[cnt].to=y;
    b[cnt].wi=z;
    f[x]=cnt;
}
void Kruskal(){
    sort(pt+1,pt+m+1,cmp);
    for(int i=1;i<=m;i++){
        int Z=pt[i];
        int from=e[Z].from,to=e[Z].to;
        int fo1=found(from),fo2=found(to);
        if(fo1!=fo2){
            fath[fo1]=fo2;
            add(from,to,e[Z].wi);add(to,from,e[Z].wi);
        }
    }
}
void dfs(int x){
    vis[x]=1;
    for(int i=f[x];i;i=b[i].nex){
        int v=b[i].to;
        if(!vis[v]){
            fa[v][0]=x;
            MI[v][0]=b[i].wi;
            deep[v]=deep[x]+1;
            for(int j=1;j<=17;j++){
                if(!fa[fa[v][j-1]][j-1])break;
                fa[v][j]=fa[fa[v][j-1]][j-1];
                MI[v][j]=min(MI[fa[v][j-1]][j-1],MI[v][j-1]);
            }
            dfs(v);
        }
    }
}
int lca(int x,int y){
    int ans=INT;
    if(deep[x]>deep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[fa[y][i]]>=deep[x])ans=min(ans,MI[y][i]),y=fa[y][i];
    if(x==y)return ans;
    for(int i=20;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
        ans=min(ans,min(MI[x][i],MI[y][i]));
        x=fa[x][i],y=fa[y][i];
        }
    }
    if(x==y)return ans;
    return min(ans,min(MI[x][0],MI[y][0]));
}
int main(){
    n=read();m=read();Q=read();
    F();
    for(int i=1;i<=m;i++){
        int x,y,z;x=read();y=read();z=read();
        fadd(x,y,z);
    }
    Kruskal();
    for(int i=1;i<=n;i++){
        if(i==found(i)){deep[i]=1;dfs(i);}
    }
    while(Q){Q--;
        int x=read(),y=read();
        int fo1=found(x),fo2=found(y);
        if(fo1!=fo2){cout<<"-1"<<endl;}
        else cout<<lca(x,y)<<endl;
    }
    return 0;
}

货车运输

除了求lca倍增以外还可以再求完最大生成树之后建一个超级树根,让超级树根连到所有的连通块的路径权值为-1

无脑从树根熟练剖分,然后线段树维护最小值

by:s_a_b_e_r

当时s看完这题一拍桌子“树链剖分啊！”

结果不管是时间复杂度还是代码复杂度都比倍增LCA高……

首先可以证明所有需要用到的边都在这张图的最大生成森林上

所以跑一遍Kruskal，只留下有用的边

然后dfs每棵树给LCA做预处理

并查集维护一下是否互相能够到达

倍增处理LCA的时候顺手处理一下路径上的最小值

以及不要一开始就加边，要Kruskal的时候再加边

因为加边之后再sort，每个点指出去的第一条边的编号会被打乱

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10009,M=50009,inf=int(1e9);
int n,m,cnt,p[N],q,fa[N],pt[N];
int f[N][20],dep[N],mi[N][20];
bool vis[N];
struct edge{int to,nex,w;}e[M<<1];
struct line{int u,v,w;}l[M];
void add(int u,int v,int w)
{
     ++cnt;
     e[cnt].to=v;
     e[cnt].nex=p[u];
     e[cnt].w=w;
     p[u]=cnt;
}
int found(int x){return x==fa[x]?x:fa[x]=found(fa[x]);}
bool cmp(line x,line y){return x.w>y.w;}
void kruskal()
{
    sort(l+1,l+m+1,cmp);
    for(int i=1;i<=m;++i)
    {
      int x=found(l[i].u),y=found(l[i].v);
      if(x!=y)
      {
        fa[x]=y;
        add(l[i].u,l[i].v,l[i].w);
        add(l[i].v,l[i].u,l[i].w);
      }
    }
}
void dfs(int u)
{
     vis[u]=1;
     for(int i=1;i<=17;++i)
     {
       if(!f[u][i-1])break;
       f[u][i]=f[f[u][i-1]][i-1];
       mi[u][i]=min(mi[u][i-1],mi[f[u][i-1]][i-1]);
     }
     for(int i=p[u];i;i=e[i].nex)
     {
       int v=e[i].to;
       if(vis[v])continue;
       dep[v]=dep[u]+1;
       f[v][0]=u;mi[v][0]=e[i].w;
       dfs(v);
     }
}
int lca(int u,int v)
{
    int ans=inf;
    if(dep[u]<dep[v])swap(u,v);
    for(int i=17;i>=0;--i)
    {
      if(dep[u]==dep[v])break;
      if(dep[f[u][i]]>=dep[v])
      {ans=min(ans,mi[u][i]);u=f[u][i];}
    }
    if(u==v)return ans;
    for(int i=17;i>=0;--i)
    {
      if(f[u][i]!=f[v][i])
      {
        ans=min(ans,min(mi[u][i],mi[v][i]));        
        u=f[u][i],v=f[v][i];
      }
    }
    ans=min(ans,min(mi[u][0],mi[v][0]));
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<=m;++i)
    scanf("%d%d%d",&l[i].u,&l[i].v,&l[i].w);
    kruskal();
    memset(mi,0x7f7f7f,sizeof(mi));
    for(int i=1;i<=n;++i)
    {
      int f=found(i);
      if(!vis[f]){dep[f]=1;dfs(f);}
    }
    scanf("%d",&q);
    while(q--)
    {
      int x,y;
      scanf("%d%d",&x,&y);
      int fx=found(x),fy=found(y);
      if(fx!=fy)cout<<-1<<endl;
      else cout<<lca(x,y)<<endl;
    }
    return 0;
}

truck

by:wypx