首页 > 代码库 > Codevs 3287 货车运输
Codevs 3287 货车运输
3287 货车运输
2013年NOIP全国联赛提高组时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond
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。
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
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。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define maxn 10010 4 #define maxm 50010 5 struct Edge{ 6 int from,to,value,next; 7 bool operator < (const Edge& a)const { 8 return value>a.value;} 9 }e[maxm],ee[maxm];10 int n,m,fa[maxn],f[maxn][21],deep[maxn],temp;11 int head[maxn],tot,Q,num,dis[maxm][21];12 void Built_Map(){13 for(int i=1,x,y,w;i<=m;i++){14 scanf("%d%d%d",&x,&y,&w);15 e[i].from=x;e[i].to=y;e[i].value=http://www.mamicode.com/w;16 }17 }18 19 int find(int x){20 if(x==fa[x]) return x;21 else return fa[x]=find(fa[x]);22 }23 void Add_Eedge(int u,int v,int w){24 ee[++num].from=u;ee[num].value=http://www.mamicode.com/w;ee[num].to=v;25 ee[num].next=head[u];head[u]=num;26 }27 void Kursual(){28 sort(e+1,e+m+1);int cur=0;29 for(int i=1;i<=n;i++) fa[i]=i;30 for(int i=1;i<=m;i++){31 int u=e[i].from,v=e[i].to;32 int rx=find(u),ry=find(v);33 if(rx != ry){34 cur++;fa[rx]=ry;35 Add_Eedge(u,v,e[i].value);36 Add_Eedge(v,u,e[i].value);37 }38 if(cur == n-1)break;39 }40 }41 void DFS(int now,int from,int deepth,int ktwo){42 f[now][0]=from;deep[now]=deepth;43 dis[now][0]=ktwo;44 for(int i=head[now];i;i=ee[i].next)45 if(ee[i].to!=from)46 DFS(ee[i].to,now,deepth+1,ee[i].value);47 }48 void Get_Fa(){49 for(int i=1;i<=17;i++)50 for(int j=1;j<=n;j++){51 f[j][i]=f[ f[j][i-1] ][i-1];52 dis[j][i]=min(dis[j][i],dis[f[j][i-1]][i-1]);53 dis[j][i]=min(dis[j][i],dis[j][i-1]);54 }55 }56 int get_same(int a,int t){57 for(int i=0;i<17;i++)58 if(t&(1<<i)){59 temp=min(temp,dis[a][i]);60 a=f[a][i];61 }62 return a;63 }64 int LCA_Judge(int u,int v){65 if(u!=1&&deep[u]==0) return -1;66 if(v!=1&&deep[v]==0) return -1;67 temp=0x3f3f3f3f;68 if(deep[u]<deep[v]) swap(u,v);69 u=get_same(u,deep[u]-deep[v]);70 if(u==v) return temp;71 for(int i=17;i>=0;i--){72 if(f[u][i]!=f[v][i]){73 temp=min(temp,dis[u][i]);74 temp=min(temp,dis[v][i]);75 u=f[u][i];v=f[v][i];76 }77 78 }79 temp=min(temp,dis[u][0]);80 temp=min(temp,dis[v][0]);81 return temp;82 }83 int main()84 {85 scanf("%d%d",&n,&m);86 memset(dis,0x3f,sizeof dis);87 Built_Map();88 Kursual();// 生成一张最大生成树 保存在ee 边表中 89 DFS(1,1,0,0);dis[1][0]=0x3f3f3f3f;90 Get_Fa();91 scanf("%d",&Q);92 for(int i=1,x,y;i<=Q;i++){93 scanf("%d%d",&x,&y);94 printf("%d\n",LCA_Judge(x,y));95 }96 return 0;97 }
思路：先跑一遍最大生成树，再通过LCA查询判断。刚是我是想查询出最近公共祖先然后从图上跑一边，查询最小值，但又觉得不太好实现，看了几位大神的博客，巧妙的处理出了dis数组，就像f数组一样，可以通过倍增处理出来，优化了不少，估计考场上能想出是最大生成树+LCA的不少，相处dis数组的没几个。
其实跑最大生成树的那个边表没必要建双向边和head数组，刚开始我全给他建上了，导致我村最大生成树的边表的head数组用link数组代替的，问题就来了，link数组，在我的IDE上没问题没交上去就CE，唉！！！！！幸亏不是考试，要是CCF的老爷机也有这毛病我就杯具了。。。
还有这是个好题，值得好好看看，好久没有敲这么长的代码了，爽!!!!!
Codevs 3287 货车运输