[NOIP2013]货车运输题解

2019-11-06 07:41:40

字体：大中小

来源：转载

供稿：网友

题目

https://www.luogu.org/PRoblem/show?pid=1967

题解

看到题是一脸懵逼，当看到因为是老师LCA练习题，所以就往LCA上想。首先，我们需要一个树才能做LCA，所以我们就套一个Kruskal最小生成树（最大版）。之后因为tarjanLCA找祖宗，虽然很快但是似乎只能找祖宗（或许因为博主是蒟蒻）所以只能用倍增LCA维护2^i的祖宗同时维护到祖宗最多运的货物，最后倍增LCA跑几遍就搞掉这道Day1T3了！！( •̀ ω •́ )y

代码

#include <cstdio>#include <cstring>#include <algorithm>#include 100];int deep[10100];struct node{ int p1,p2,l;}info[50100];bool cmp(node a,node b){ return a.l > b.l;}int find(int x){ if(kfa[x] == x)return x; return kfa[x] = find(kfa[x]);}void add(int f,int t,int l){ to[++tot]= t; lim[tot] = l; nxt[tot] = head[f]; head[f] = tot;}void dfs(int pos,int pre){ deep[pos] = deep[pre] + 1; for(int i = head[pos];i;i = nxt[i]) if(to[i] != pre){ dfs(to[i],pos); fa[to[i]][0][0] = pos,fa[to[i]][0][1] = lim[i]; }}int lim_lca(int x,int y){ int dis1 = 0x7fffffff,dis2 = 0x7fffffff; if(deep[x]= 0;i--) if(deep[fa[x][i][0]] >= deep[y]) dis1 = min(fa[x][i][1],dis1),x=fa[x][i][0]; if(x==y) return dis1; for(int i=16;i>=0;i--) if(fa[x][i][0] != fa[y][i][0]) dis1 = min(fa[x][i][1],dis1),dis2 = min(fa[y][i][1],dis2),x = fa[x][i][0],y = fa[y][i][0]; return min(min(dis1 , dis2) , min(fa[x][0][1] , fa[y][0][1]));}int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= m;i++) scanf("%d%d%d",&info[i].p1,&info[i].p2,&info[i].l); sort(info + 1,info + 1 + m,cmp); for(int i = 1;i <= n;i++)kfa[i] = i; for(int i = 1;i <= m;i++){ int fax = find(info[i].p1); int fay = find(info[i].p2); if(fax != fay){ kfa[fax] = fay; add(info[i].p1,info[i].p2,info[i].l); add(info[i].p2,info[i].p1,info[i].l); } } dfs(1,0); for(int j = 1;j <= 16;j++) for(int i = 1;i <= n;i++){ fa[i][j][0] = fa[fa[i][j - 1][0]][j - 1][0]; fa[i][j][1] = min(fa[fa[i][j - 1][0]] i = head[pos];i;i = nxt[i]) if(to[i] != pre){ dfs(to[i],pos); fa[to[i]][0][0] = pos,fa[to[i]][0][1] = lim[i]; }}int lim_lca(int x,int y){ int dis1 = 0x7fffffff,dis2 = 0x7fffffff; if(deep[x]<deep[y]) swap(x,y); for(int i = 16;i >= 0;i--) if(deep[fa[x][i][0]] >= deep[y]) dis1 = min(fa[x][i][1],dis1),x=fa[x][i][0]; if(x==y) return dis1; for(using namespace std;int n,m,que;int head[10100],nxt[20100],lim[20100],to[20100],tot;int fa[10100][21][2];int kfa[10100];int deep[10100];struct node{ int p1,p2,l;}info[50100];bool cmp(node a,node b){ return a.l > b.l;}int find(int x){ if(kfa[x] == x)return x; return kfa[x] = find(kfa[x]);}void add(int f,int t,int l){ to[++tot]= t; lim[tot] = l; nxt[tot] = head[f]; head[f] = tot;}void dfs(int pos,int pre){ deep[pos] = deep[pre] + 1; for(intSE,cmp); for(int i = 1;i <= n;i++)kfa[i] = i; for(int i = 1;i <= m;i++){ int fax = find(info[i].p1); int fay = find(info[i].p2); if(fax != fay){ kfa[fax] = fay; add(info[i].p1,info[i].p2,info[i].l); add(info[i].p2,info[i].p1,info[i].l); } } dfs(1,0); for(int j = 1;j <= 16;j++) for(int i = 1;i <= n;i++){ fa[i][j][0] = fa[fa[i][j - 1][0]][j - 1][0]; fa[i][j][1] = min(fa[fa[i][j - 1][0]][j - 1][1],fa[i][j - 1][1]); } scanf("%d",&que); for(int i = 1;i <= que;i++){ int x,y; scanf("%d%d",&x,&y); int ans = lim_lca(x,y); if(ans) printf("%d/n",ans); else printf("-1/n"); }}

上一篇：算法基础之插入排序

下一篇：【Linux】gdb下调试多线程