NOIp2013 货车运输 By cellur925

题目传送门

A 国有 n 座城市，编号从 1 到 n ，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

思路

这题思路想明白了就很简单，一句话题意：求树上两点间路线中边长最小的边权。

首先，为什么是树呢？限重肯定越大越好，因此我们可以跑出图的最大生成树（Kruskal）

之后，我们就可以对于每次询问来求出路径上的最小边权（最多能运的货物重量），这里可以用到树上倍增法（求LCA时一起求了，虽然LCA不会直接用到，但也是要一起求出来的）

至于两点间是否能互达，就可以用并查集维护一下就行了！

实现

提交记录过于真实，从0到10到65到70到95到AC Orz

可能是我常数写丑了，所以在洛谷更新评测姬前以及不开氧气优化都会T两个点？？

code

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #include<cstring>

 #define maxm 50090

 #define maxn 10090

 using namespace std;

 int n,m,Q,tot,t;

 int head[maxn],d[maxn],f[maxn][],fa[maxn],g[maxn][];

 bool vis[maxn];

 struct cellur{

     int f,t,w;

 }e[maxm];

 struct node{

     int to,next,val;

 }edge[maxn<<];

 bool cmp(cellur a,cellur b)

 {

     return a.w>b.w;

 } 

 void add(int x,int y,int z)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

     edge[tot].val=z;

 }

 int getf(int x)

 {

     if(fa[x]==x) return x;

     else return fa[x]=getf(fa[x]);

 }

 void Kruskal()

 {

     for(int i=;i<=n;i++) fa[i]=i;

     sort(e+,e++m,cmp);

     int cnt=;

     for(int i=;i<=m;i++)

     {

         if(cnt==n-) break;

         int pp=getf(e[i].f);

         int qq=getf(e[i].t);

         if(pp==qq) continue;

         cnt++;

         fa[qq]=pp;

         add(e[i].f,e[i].t,e[i].w),add(e[i].t,e[i].f,e[i].w);

     }

 }

 void bfs(int s)

 {

     queue<int>q;

     q.push(s);d[s]=;

     while(!q.empty())

     {

         int u=q.front();q.pop();

         for(int i=head[u];i;i=edge[i].next)

         {

             int v=edge[i].to;

             if(d[v]) continue;

             d[v]=d[u]+;

             f[v][]=u;g[v][]=edge[i].val;

             for(int j=;j<=t;j++)

             {

                 f[v][j]=f[f[v][j-]][j-];

                 g[v][j]=min(g[f[v][j-]][j-],g[v][j-]);

             }

             q.push(v);

         }

     }

 }

 int lca(int x,int y)

 {

     int num=1e9;

     if(d[x]<d[y]) swap(x,y);

     for(int i=t;i>=;i--)

         if(d[f[x][i]]>=d[y]) num=min(num,g[x][i]),x=f[x][i];

     if(x==y) return num;

     for(int i=t;i>=;i--)

         if(f[x][i]!=f[y][i])

         {

             num=min(num,g[x][i]);

             num=min(num,g[y][i]);

             x=f[x][i],y=f[y][i];

         }

     return min(num,min(g[x][],g[y][]));

 }

 int main()

 {

     freopen("truck.in","r",stdin);

     freopen("truck.out","w",stdout);

     scanf("%d%d",&n,&m);

     t=log2(n)+;

     for(int i=;i<=m;i++)

         scanf("%d%d%d",&e[i].f,&e[i].t,&e[i].w);

     Kruskal();

     memset(g,,sizeof(g));

     for(int i=;i<=n;i++) if(!d[i]) bfs(i);

 //    for(int i=1;i<=n;i++) printf("%d ",g[i][2]);

 //    return 0;

     scanf("%d",&Q);

     while(Q--)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         int pp=getf(x);

         int qq=getf(y);

         if(pp!=qq) {printf("-1\n");continue;}

         printf("%d\n",lca(x,y));

     }

     return ;

 }

$bfs$也能解决不连通的问题：不bfs一次，而是让每个点都有深度。

11.6考试的时候边大小开小了&&LCA写错板子了hhh

巴特西

NOIp2013 货车运输 By cellur925

最新文章

热门文章