P1967 货车运输

题目描述

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入输出格式

输入格式:

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y,两座城市之间可能有多条道路

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y

输出格式:

输出文件名为 truck.out。

输出共有 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。

和这道题熬战总计7.5小时后终于调试出来了!!

思路我就不多说了,跑一边最大树然后倍增求LCA不断取最小值就好

我在这里说一下这道题容易犯的错误

1.在读入第一个图的时候必须用有向边储存,但是跑最大生成树产生的图必须用无向图储存

2.在选择源点的时候可以从1->n进行dfs,但是必须要开一个vis数组,单纯一个deep数组是不可以的

3.在从低处点往高处点跳的时候判断条件一定是deep[s[x][i]]>=deep[y],必须是>=!!!

4.在取最小值得时候一定是在更新变量之前取!!

5.注意各种变量的初始化!

因为调试时间比较长,所以代码可以比较长,但没什么高大上的语句,写的还算简单

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 using namespace std;
  7 const int MAXN=50001;
  8 int n,m;
  9 int x,y,z;
 10 int vis[MAXN];
 11 struct node
 12 {
 13     int u,v,w,next;
 14 }edge[MAXN],a[MAXN];
 15 int num=1;
 16 int head[MAXN];
 17 int f[MAXN];
 18 int anum=1;
 19 int ahead[MAXN];
 20 int deep[MAXN];
 21 int s[MAXN][20];
 22 int take[MAXN][20];
 23 void edge_add(int x,int y,int z)
 24 {
 25     edge[num].u=x;
 26     edge[num].v=y;
 27     edge[num].w=z;
 28     edge[num].next=head[x];
 29     head[x]=num++;
 30 }
 31 void a_add(int i)
 32 {
 33     a[anum].u=edge[i].u;
 34     a[anum].v=edge[i].v;
 35     a[anum].w=edge[i].w;
 36     a[anum].next=ahead[a[anum].u];
 37     ahead[a[anum].u]=anum++;
 38     a[anum].u=edge[i].v;
 39     a[anum].v=edge[i].u;
 40     a[anum].w=edge[i].w;
 41     a[anum].next=ahead[a[anum].u];
 42     ahead[a[anum].u]=anum++;
 43 }
 44 int comp(const node & a ,const node & b)
 45 {return a.w>b.w;}
 46 
 47 int find(int x)
 48 {
 49     if(f[x]!=x)
 50     f[x]=find(f[x]);
 51     return f[x];
 52 }
 53 void unionn(int x,int y)
 54 {
 55     int fx=find(x);
 56     int fy=find(y);
 57     f[fx]=fy;
 58 }
 59 void Biggest_Kruskal()
 60 {
 61     sort(edge+1,edge+num+1,comp);
 62     int k=0;
 63     for(int i=1;i<=num;i++)
 64     {
 65         int uu=edge[i].u;
 66         int vv=edge[i].v;
 67         if(find(uu)!=find(vv))
 68         { 
 69             a_add(i);
 70             unionn(uu,vv);
 71             k++;
 72         }
 73         if(k==n-1)break;
 74     }
 75     //for(int i=1;i<=anum;i++)
 76     //    cout<<a[i].u<<" "<<a[i].v<<" "<<a[i].w<<" "<<a[i].next<<endl;
 77 }
 78 void Build_Tree(int p)
 79 {
 80     vis[p]=1;
 81     for(int i=ahead[p];i!=-1;i=a[i].next)
 82     {
 83          int will=a[i].v;
 84         if(vis[will])continue;
 85         vis[will]=1;
 86        
 87             deep[will]=deep[p]+1;
 88             s[will][0]=p;
 89             take[will][0]=a[i].w;
 90             Build_Tree(will);
 91     }
 92 }
 93 void Initialize_Step()
 94 {
 95     for(int i=1;i<=18;i++)
 96     {
 97         for(int j=1;j<=n;j++)
 98         {
 99             s[j][i]=s[s[j][i-1]][i-1];
100             take[j][i]=min(take[j][i-1],take[s[j][i-1]][i-1]);
101         }
102     }
103 }
104 int LCA(int x,int y)
105 {
106     int ans=0x7ffffff;
107     if(deep[x]<deep[y])
108     swap(x,y);
109     for(int i=18;i>=0;i--)
110     {
111         if(s[x][i]!=0)
112         if(deep[s[x][i]]>=deep[y])
113         {
114             ans=min(ans,take[x][i]);
115             x=s[x][i];    
116         }
117     }
118     if(x==y)
119     return ans;
120     for(int i=18;i>=0;i--)
121     {
122         if(s[x][i]!=s[y][i])
123         {
124             ans=min(ans,take[x][i]);
125             ans=min(ans,take[y][i]);
126             x=s[x][i];
127             y=s[y][i];
128         }
129     }
130     ans=min(ans,take[x][0]);
131     ans=min(ans,take[y][0]);
132     return ans;
133 }
134 int main()
135 {
136 //    memset(take,0xf,sizeof(take));
137     scanf("%d%d",&n,&m);
138     
139     for(int i=1;i<=n;i++)
140     {head[i]=-1;f[i]=i;ahead[i]=-1;}
141     
142     for(int i=1;i<=m;i++)
143     {
144         scanf("%d%d%d",&x,&y,&z);
145         edge_add(x,y,z);
146         //edge_add(y,x,z);
147     }
148     Biggest_Kruskal();
149     //deep[1]=1;
150     for(int i=1;i<=n;i++)
151     {
152         if(vis[i]==0)
153         Build_Tree(i);
154     }
155     
156     Initialize_Step();
157     int q;
158     scanf("%d",&q);
159     for(int i=1;i<=q;i++)
160     {
161         int x,y;
162         scanf("%d%d",&x,&y);
163         if(find(x)!=find(y))
164         {
165             printf("-1\n");
166             continue;
167         }
168         printf("%d\n",LCA(x,y));
169     }
170     return 0;
171 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • P2746 [USACO5.3]校园网Network of Schools

    题目描述 一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A...

    attack
  • HDU5036 Explosion(期望 bitset)

    首先根据期望的线性性,可以转化为求每个点的期望打开次数,又因为每个点最多会被打开一次,只要算每个点被打开的概率就行了

    attack
  • P1113 杂务 拓扑

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • 2034-人见人爱A-B(c++实现)

    参加过上个月月赛的同学一定还记得其中的一个最简单的题目,就是{A}+{B},那个题目求的是两个集合的并集,今天我们这个A-B求的是两个集合的差,就是做集合的减法...

    用户2038589
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack
  • 1038 统计同成绩学生 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051

扫码关注云+社区

领取腾讯云代金券