首页 > 代码库 > 3287 货车运输 2013年NOIP全国联赛提高组 40 分
3287 货车运输 2013年NOIP全国联赛提高组 40 分
3287 货车运输
2013年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入描述 Input Description
第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意:x 不等于 y。
输出描述 Output Description
输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。
样例输入 Sample Input
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
样例输出 Sample Output
3
-1
3
数据范围及提示 Data Size & Hint
对于 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。
分类标签 Tags 点此展开
I am Fade
I am a mengbier
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int MAXN= 50001; 8 struct node 9 { 10 int u; 11 int v; 12 int w; 13 int nxt; 14 }edge[MAXN]; 15 int head[MAXN]; 16 int num=1; 17 int numm; 18 int n,m,q; 19 int f[MAXN]; 20 int anc[30001][300],len[30001][300],dep[30001]; 21 int maxnb; 22 int que[MAXN]; 23 int vis[MAXN]; 24 void BFSforLCA(int o) 25 { 26 memset(vis,0,sizeof(vis)); 27 memset(que,0,sizeof(que)); 28 int i; 29 int h=0,t=1; 30 que[0]=o; 31 vis[o]=1; 32 len[o][0]=0x7fff; 33 for(;h<t;h++) 34 { 35 int u=que[h]; 36 for(int j=head[u];j!=-1;j=edge[j].nxt) 37 { 38 int v=edge[j].v;int w=edge[j].w; 39 if(vis[v]==1)continue; 40 vis[v]=1; que[t]=v; t++; 41 anc[v][0]=u; len[v][0]=w; dep[v]=dep[u]+1; 42 } 43 } 44 } 45 void InitializtionForLCA() 46 { 47 for(int j=0;(1<<j)<n;j++) 48 { for(int i=0;i<=n;i++) 49 { 50 anc[i][j+1]=anc[anc[i][j]][j]; 51 len[i][j+1]=min(len[anc[i][j]][j],len[i][j]); 52 } 53 maxnb=j;} 54 } 55 int LCA(int u,int v) 56 { 57 int i,j; 58 if(dep[u]<dep[v])swap(u,v); 59 int ans=0x7fffff; 60 //cout<<dep[u]<<"**"<<dep[v]<<endl; 61 for(int i=maxnb;i>=0;i--) 62 { 63 int p=anc[u][i]; 64 if(dep[anc[u][i]]>=dep[v]) 65 { 66 //cout<<dep[anc[u][i]]<<" "<<dep[v]<<endl; 67 ans=min(ans,len[u][i]); 68 u=anc[u][i]; 69 } 70 } 71 for(int i=maxnb;i>=0;i--) 72 { 73 if(anc[u][i]!=anc[v][i]) 74 { 75 ans=min(ans,min(len[u][i],len[v][i])); 76 u=anc[u][i];v=anc[v][i]; 77 } 78 } 79 if(u!=v) 80 { 81 ans=min(ans,min(len[u][0],len[v][0])); 82 u=anc[u][0];v=anc[v][0]; 83 } 84 return ans; 85 } 86 87 int comp(const node & a,const node & b) 88 {return a.w>b.w;} 89 int find(int x) 90 {if(f[x]!=x)return f[x]=find(f[x]);return f[x];} 91 int unionn(int x,int y) 92 {int fx=find(x);int fy=find(y);f[fx]=fy;} 93 94 void Kruskal() 95 { 96 sort(edge+1,edge+num,comp); 97 numm=num;//储存边的个数,把最大生成树存到edge上 98 int k=0; 99 for(int i=1;i<=numm;i++)100 {101 if(find(edge[i].u)!=find(edge[i].v))102 {103 k++;104 unionn(edge[i].u,edge[i].v);105 edge[num].u=edge[i].u;edge[num].v=edge[i].v;edge[num].w=edge[i].w;106 edge[num].nxt=head[edge[num].u];107 head[edge[num].u]=num++;108 edge[num].u=edge[num-1].v;edge[num].v=edge[num-1].u;edge[num].w=edge[num-1].w;109 edge[num].nxt=head[edge[num].u];110 head[edge[num].u]=num++;111 //edge[numm+edge[i].u].u=edge[i].u;edge[num+edge[i].u].v=edge[i].v;edge[num+edge[i].u++].w=edge[i].w;112 }113 if(k==n-1)break;114 }115 }116 int main()117 {118 scanf("%d%d",&n,&m);119 for(int i=1;i<=n;i++)head[i]=-1,f[i]=i;120 for(int i=1;i<=m;i++)121 {122 cin>>edge[num].u>>edge[num].v>>edge[num].w;num++;123 }124 Kruskal();125 for(int i=1;i<=n;i++)126 //if(vis[i])127 BFSforLCA(i);128 InitializtionForLCA();// 初始化父子关系 129 /*for(int i=1;i<=n;i++)130 cout<<anc[i][0]<<" ";131 cout<<endl<<"*******************"<<endl;132 for(int i=1;i<=n;i++)133 for(int j=head[i];j!=-1;j=edge[j].nxt)134 cout<<edge[j].u<<"->"<<edge[j].v<<endl;135 */136 scanf("%d",&q);137 int x,y;138 for(int i=1;i<=q;i++)139 {140 scanf("%d%d",&x,&y);141 int p=LCA(x,y);142 if(find(x)!=find(y))143 printf("-1\n");144 else printf("%d\n",p);145 }146 return 0;147 }
3287 货车运输 2013年NOIP全国联赛提高组 40 分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。