首页 > 代码库 > P1967 货车运输
P1967 货车运输
P1967 货车运输
题目描述
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+最大生成树（路的限重越大越好）
上代码：
1.
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define INF 1000000000#define MAXM 50010#define MAXN 10010struct node { int x,y,v;} E[MAXM];struct node2 { int y,next,v;} e[MAXN*2];int n,m,q,len;int vis[MAXN],f[MAXN],Link[MAXN],deep[MAXN],anc[MAXN][25],w[MAXN][25];inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f;}bool cmp(node a,node b) { return a.v>b.v;}int find(int x) { return f[x]==x?x:f[x]=find(f[x]);}void insert(int x,int y,int v) { e[++len].next=Link[x]; Link[x]=len; e[len].y=y; e[len].v=v;}void dfs(int x) { //计算深度 vis[x]=1; for(int i=1; i<=20; i++) { anc[x][i]=anc[anc[x][i-1]][i-1]; w[x][i]=min(w[x][i-1],w[anc[x][i-1]][i-1]); } for(int i=Link[x]; i; i=e[i].next) if(!vis[e[i].y]) { deep[e[i].y]=deep[x]+1; anc[e[i].y][0]=x; w[e[i].y][0]=e[i].v; dfs(e[i].y); }}int lca(int x,int y) { //求LCA if(deep[x]<deep[y]) swap(x,y); for(int i=20; i>=0; i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i]; if(x==y) return x; for(int i=20; i>=0; i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i]; return anc[x][0];}int ask(int x,int f) { //求路径上的最小值 int mn=INF; int t=deep[x]-deep[f]; for(int i=0; i<=16; i++) if(t&(1<<i)) { //1<<i一定为真，所以要求t为真 mn=min(mn,w[x][i]); x=anc[x][i]; } return mn;}int main() { memset(w,127/3,sizeof(w)); n=read(); m=read(); for(int i=1; i<=m; i++) { E[i].x=read(); E[i].y=read(); E[i].v=read(); } sort(E+1,E+m+1,cmp); for(int i=1; i<=n; i++) f[i]=i; for(int i=1; i<=m; i++) { int x=find(E[i].x),y=find(E[i].y); if(x!=y) { f[x]=y; insert(E[i].x,E[i].y,E[i].v); insert(E[i].y,E[i].x,E[i].v); } } for(int i=1; i<=n; i++) if(!vis[i]) dfs(i); q=read(); for(int i=1; i<=q; i++) { int x=read(),y=read(); if(find(x)!=find(y)) { printf("-1\n"); continue; } int t=lca(x,y); printf("%d\n",min(ask(x,t),ask(y,t))); } return 0;}
2.
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define maxn 10010#define maxm 50010int n,m,f[maxn][20],sum[maxn][20],fa[maxn],num,p,dep[maxn],head[maxn];bool vis[maxn];struct node { int f,to,v;} a[maxm];struct Edge { int pre,v,to;} e[maxm];int cmp(node x,node y) { return x.v>y.v;}int find(int x) { if(fa[x]==x)return fa[x]; else return fa[x]=find(fa[x]);}int connect(int x,int y) { int f1=find(x),f2=find(y); if(f1==f2)return 0; else fa[f1]=f2; return 1;}void Insert(int from,int to,int v) { e[++num].v=v; e[num].to=to; e[num].pre=head[from]; head[from]=num;}void dfs(int now,int father,int deep) { vis[now]=1; dep[now]=deep; for(int i=head[now]; i; i=e[i].pre) { int v=e[i].to; if(v==father)continue; f[v][0]=now; sum[v][0]=e[i].v; dfs(v,now,deep+1); }}int lca(int x,int y) { if(x==y)return 0; int ans=0x3f3f3f3f; if(dep[x]<dep[y])swap(x,y); for(int i=18; i>=0; i--) { if(dep[f[x][i]]>=dep[y]&&f[x][i]!=0) ans=min(ans,sum[x][i]),x=f[x][i]; } if(x==y)return ans; for(int i=18; i>=0; i--) { if(f[x][i]!=f[y][i]) { ans=min(ans,sum[x][i]); ans=min(ans,sum[y][i]); x=f[x][i]; y=f[y][i]; } } ans=min(sum[x][0],ans); ans=min(sum[y][0],ans); return ans;}int main() { memset(sum,127/3,sizeof(sum)); int x,y,z; scanf("%d%d",&n,&m); for(int i=1; i<=m; i++)scanf("%d%d%d",&a[i].f,&a[i].to,&a[i].v); for(int i=1; i<=n; i++)fa[i]=i; sort(a+1,a+m+1,cmp); int cnt=0; for(int i=1; i<=m; i++) { if(connect(a[i].f,a[i].to)) { Insert(a[i].f,a[i].to,a[i].v); Insert(a[i].to,a[i].f,a[i].v); cnt++; if(cnt==n-1)break; } } for(int i=1; i<=n; i++)if(!vis[i])dfs(i,0,1); for(int j=1; (1<<j)<=n; j++) for(int i=1; i<=n; i++) if(f[f[i][j-1]][j-1]!=0) { f[i][j]=f[f[i][j-1]][j-1]; sum[i][j]=min(sum[i][j-1],sum[f[i][j-1]][j-1]); } scanf("%d",&p); for(int i=1; i<=p; i++) { scanf("%d%d",&x,&y); if(find(x)!=find(y)) { printf("-1\n"); continue; } printf("%d\n",lca(x,y)); }}
自己选的路，跪着也要走完！！！
P1967 货车运输
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。