首页 > 代码库 > NOIP 2013 货车运输
NOIP 2013 货车运输
题目描述
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 31 2 42 3 33 1 131 31 41 3
输出样例#1：
3-13
说明
对于 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。、
最大生成树存图+树剖求lca
如果在同一棵树里面，求出lca，并求两个点到lca的最小权值边，我用的线段树。如果不在一棵树则输出-1。
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define INF 0x7f7f7f7f#define N 50004 int n,m;int dad[N],deep[N],sum[N*2];int head[N],size[N],top[N]; int far[N*4],wson[N];int cnt=0;int pre[N],tops[N];int num=1;int father[N];struct node{ int v,next,w;}edge[N*5];struct Edge{ int x,z;int y; bool operator < (const Edge & a)const{ return z>a.z; }}e[N*5];int find(int x){ if(father[x]!=x)father[x]=find(father[x]); return father[x];}void add_edge(int x,int y,int w){ edge[num].v=y; edge[num].w=w; edge[num].next=head[x]; head[x]=num++;}void kruskal(){ sort(e+1,e+m+1); for(int i=1;i<=n;i++)father[i]=i; for(int i=1;i<=m;i++) { if(find(e[i].x) != find(e[i].y)) { add_edge(e[i].x,e[i].y,e[i].z); add_edge(e[i].y,e[i].x,e[i].z); father[find(e[i].x)]=find(e[i].y); } }}void dfs1(int x,int y){ size[x]=1; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].v; if(v==y)continue; deep[v]=deep[x]+1; dad[v]=x; far[v]=edge[i].w; dfs1(v,x); size[x]+=size[v]; if(size[v]>size[wson[x]])wson[x]=v; }}void dfs2(int u,int topp){ tops[u]=++cnt;pre[cnt]=u;top[u]=topp; if(wson[u])dfs2(wson[u],topp); for(int i=head[u];i;i=edge[i].next) { int v=edge[i].v; if(v==dad[u]||v==wson[u])continue; dfs2(v,v); }}void update(int rt){ sum[rt]=min(sum[rt*2],sum[rt*2+1]);}void build(int l,int r,int rt){ if(l==r) { sum[rt]=far[pre[l]]; return ; } int mid=(l+r)/2; build(l,mid,rt*2); build(mid+1,r,rt*2+1); update(rt);}int query_min(int l,int r,int ql,int qr,int rt){ if(l>r)return 2147483647; int mid=(l+r)/2,ans=INF; if(ql<=l&&qr>=r)return sum[rt]; if(ql<=mid)ans=min(ans,query_min(l,mid,ql,qr,rt*2)); if(qr>mid)ans=min(ans,query_min(mid+1,r,ql,qr,rt*2+1)); return ans;}int LCA(int u,int v){ int ans=INF; while(top[u]!=top[v]) { if(deep[top[u]]<deep[top[v]])swap(u,v); ans=min(ans,query_min(1,n,tops[top[u]],tops[u],1)); u=dad[top[u]]; } if(deep[u]<deep[v])swap(u,v); ans=min(ans,query_min(1,n,tops[v]+1,tops[u],1)); return ans;}int main(){ scanf("%d%d",&n,&m); memset(far,-1,sizeof far); for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); } kruskal(); dfs1(1,0); dfs2(1,1); build(1,n,1); int q; scanf("%d",&q); int x,y; while(q--) { int x,y; scanf("%d%d",&x,&y); int xx=find(x),yy=find(y); if(xx!=yy)printf("-1\n"); else printf("%d\n",LCA(x,y)); } return 0;}
NOIP 2013 货车运输
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。