首页 > 代码库 > [luogu P1967][NOIp2013]P1967 货车运输
[luogu P1967][NOIp2013]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。
因为这题在bzoj里又是那啥啥，所以就又交luogu了
代码这么长又比别人慢真是太尴尬了
这么慢思路肯定很easy对吧
->先求用kruskal最大生成树，可忽略重边问题
->以重心为根造树
->对于每一组询问(ss,tt)，求其lca
->我这边模拟了它从ss和tt走到lca，程序秒速变慢 QwQ(懒癌晚期)
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<vector> 5 #include<algorithm> 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 #define ss first 9 #define tt second 10 11 inline int read(){ 12 char ch; 13 int re=0; 14 bool flag=0; 15 while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘)); 16 ch==‘-‘?flag=1:re=ch-‘0‘; 17 while((ch=getchar())>=‘0‘&&ch<=‘9‘) re=re*10+ch-‘0‘; 18 return flag?-re:re; 19 } 20 21 struct odge{ 22 int from,to,w; 23 odge(int from=0,int to=0,int w=0): 24 from(from),to(to),w(w){} 25 bool operator < (const odge &n1) const { 26 return w>n1.w; 27 } 28 }; 29 struct edge{ 30 int to,w,next; 31 edge(int to=0,int w=0,int next=0): 32 to(to),w(w),next(next){} 33 }; 34 const int maxn=10001,maxm=50001; 35 const int maxlogn=14; 36 int n,m; 37 vector<odge> odges; 38 vector<edge> edges; 39 int head[maxn]; 40 int par[maxn]; 41 int cnt=0; 42 int F[maxn],son[maxn]; 43 bool vis[maxn]; 44 int sum,root; 45 int depth[maxn],parent[maxlogn][maxn]; 46 int q; 47 typedef pair<int,int> PII; 48 vector<PII> ques; 49 int length[maxn]; 50 51 inline void add_edge(odge e){ 52 edges.push_back(edge(e.to,e.w,head[e.from])); 53 head[e.from]=++cnt; 54 edges.push_back(edge(e.from,e.w,head[e.to])); 55 head[e.to]=++cnt; 56 } 57 58 int find(int x){ 59 return par[x]==x?x:par[x]=find(par[x]); 60 } 61 62 void kruskal(){ 63 memset(head,0,sizeof head); 64 edges.push_back(edge(0,0,0)); 65 int cnt1=1,cnt2=0; 66 while(cnt2<m){ 67 odge e=odges[cnt2++]; 68 int dx=find(e.from),dy=find(e.to); 69 if(dx==dy) continue; 70 add_edge(e); 71 par[dy]=dx; 72 if(++cnt1==n) break; 73 } 74 } 75 76 void getroot(int x,int fa){ 77 son[x]=1; F[x]=0; 78 for(int ee=head[x];ee;ee=edges[ee].next) 79 if(edges[ee].to!=fa){ 80 getroot(edges[ee].to,x); 81 son[x]+=son[edges[ee].to]; 82 F[x]=max(F[x],son[edges[ee].to]); 83 } 84 F[x]=max(F[x],sum-son[x]); 85 if(F[x]<F[root]) root=x; 86 } 87 88 void dfs(int x,int fa,int deep){ 89 parent[0][x]=fa; 90 depth[x]=deep; 91 for(int ee=head[x];ee;ee=edges[ee].next) 92 if(edges[ee].to!=fa){ 93 length[edges[ee].to]=edges[ee].w; 94 dfs(edges[ee].to,x,deep+1); 95 } 96 } 97 98 void init(){ 99 n=read(); m=read();100 for(int i=0;i<m;i++){101 int from=read(),to=read(),w=read();102 odges.push_back(odge(from,to,w));103 }104 for(int i=1;i<=n;i++)105 par[i]=i;106 sort(odges.begin(),odges.end());107 kruskal();108 sum=F[root=0]=n;109 getroot(1,0);110 dfs(root,-1,0);111 for(int k=0;k+1<maxlogn;k++)112 for(int v=1;v<=n;v++)113 if(parent[k][v]<0) parent[k+1][v]=-1;114 else parent[k+1][v]=parent[k][parent[k][v]];115 q=read();116 for(int i=0;i<q;i++){117 int from=read(),to=read();118 ques.push_back(make_pair(from,to));119 }120 }121 122 int getlca(int u,int v){123 if(depth[u]>depth[v]) swap(u,v);124 for(int k=0;k<maxlogn;k++)125 if(depth[v]-depth[u]>>k&1) v=parent[k][v];126 if(u==v) return u;127 for(int k=maxlogn-1;k>=0;k--)128 if(parent[k][u]!=parent[k][v]){129 u=parent[k][u];130 v=parent[k][v];131 }132 return parent[0][u];133 }134 135 void solve(){136 for(int i=0;i<q;i++){137 int u=ques[i].ss,v=ques[i].tt;138 if(find(u)!=find(v)){139 puts("-1");140 continue;141 }142 int ans=inf;143 int lca=getlca(ques[i].ss,ques[i].tt);144 145 while(u!=lca){146 ans=min(ans,length[u]);147 u=parent[0][u];148 }149 while(v!=lca){150 ans=min(ans,length[v]);151 v=parent[0][v];152 }153 154 printf("%d\n",ans);155 }156 }157 158 int main(){159 //freopen("temp.in","r",stdin);160 init();161 solve();162 return 0;163 }
天亮的时候 你还没回来
亲爱的 我们的孩子醒来了
[luogu P1967][NOIp2013]P1967 货车运输
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。