P1967 货车运输

2018-06-17 22:39:07来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:网络编程:I/O模型

下一篇:P3374 【模板】树状数组 1 单点修改与区间查询