【codevs 3287】货车运输

在最大生成树上搞lca来维护最小值。
打了大半天，改了好多才勉强弄出来QAQ……Orz神犇们。
注意：
1.图和树分开存。
2.输出判断时不要乱搞什么if(ans==0x3f3f3f3f)..真的会wa的。

#include
#include
#include
#include
#include
using namespace std;
int n,m,times;
const int maxn=50000+5;
int cnt=0,tot=0,first[maxn],next[maxn<<1];
int fa[maxn][35],pa[maxn],rank[maxn];
int deep[maxn],coss[maxn][35];
struct edge
{int f,t,v;
}es[maxn<<1],ess[maxn<<1];//图存es，树存ess 
void build(int f,int t,int v) 
{ess[++tot]=(edge){f,t,v};next[tot]=first[f];first[f]=tot;return;
}
bool cmp(edge a,edge b)
{return a.v>b.v;
}
int find(int x)
{return pa[x]==x?x:pa[x]=find(pa[x]);
}
void merge(int x,int y)
{if(rank[x]==rank[y]) {pa[x]=y;rank[y]++;}else if(rank[x]>rank[y]) pa[y]=x;else pa[x]=y;
}
void kruskal()
{sort(es+1,es+1+cnt,cmp);for(int i=1;i<=n;i++){pa[i]=i;rank[i]=0;}for(int i=1;i<=cnt;i++){int x=find(es[i].f),y=find(es[i].t);if(x!=y) {merge(x,y);build(es[i].f,es[i].t,es[i].v);build(es[i].t,es[i].f,es[i].v);}}return;
}
void dfs(int x,int y)
{for(int i=first[x];i;i=next[i]){int at=ess[i].t,av=ess[i].v;if(at==y) continue;fa[at][0]=x;coss[at][0]=av;deep[at]=deep[x]+1;dfs(at,x);}return;
} 
void make_lca()
{for(int i=1;i<=log2(n);i++)for(int j=1;j<=n;j++){fa[j][i]=fa[fa[j][i-1]][i-1];coss[j][i]=min(coss[j][i-1],coss[fa[j][i-1]][i-1]);}return;
}
int lca(int x,int y)
{if(deep[x]for(int i=log2(n);i>=0;i--){if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];}if(x==y) return x;for(int i=log2(n);i>=0;i--){if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];}return fa[x][0];
}
int ask(int a,int b)
{int ans=0x3f3f3f3f;for(int i=log2(n);i>=0;i--){if(deep[fa[a][i]]>=deep[b]) {ans=min(ans,coss[a][i]);a=fa[a][i];}}return ans;
}
int main()
{memset(coss,0x3f3f3f3f,sizeof(coss));scanf("%d%d",&n,&m);int x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);es[++cnt]=(edge){x,y,z};//cnt:图的边数 es[++cnt]=(edge){y,x,z};}kruskal();dfs(1,1);make_lca();scanf("%d",×);int ans;    while(times--){scanf("%d%d",&x,&y);if(find(x)!=find(y)) cout<<-1<else {int LCA=lca(x,y);ans=min(ask(x,LCA),ask(y,LCA));cout<return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！