首页 > > 程序设计 > C/C++ >

P1967 货车运输

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

题目描述

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：

输出样例#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 }