NOIP 2013 【货车运输】

【题目大意】给定一张无向图 以及若干个询问 对于每个询问求所有由节点u到节点v的路径上边权的最小值的最大值。

【题解】

  首先用构造一棵最大生成树，这样保证树上两个节点路径边权的最小值最大

  在最大生成树上两个节点之间只有一条路径，所以只需要找路径上边权的最小值

 为了快速的寻找最小值，利用树上倍增的想法用f[j][i]记录j的第2^i个祖先 并用 g[j][i]记录j到f[j][i]的路径上边权的最小值

 然后在找公共祖先时顺便就能处理最小值

【注意】可能不是一张连通图，所有在lca时记得判断两个点是不是在同一棵树里

 详见代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int i,j,k,l,m,n,fx,fy,q,x,y,z,num;
int fa[10005],up[10005][20],first[10005],g[10005][20],h[10005];
struct info{int fr,ar,l,next;}road[100050],tree[20005];
//vector  tree[10005];
bool cmp(info x,info y) {return x.l>y.l;}
int getfa(int x){if(fa[x]==x) return x;else return fa[x]=getfa(fa[x]);}
void dfs(int u){int i,v;for (i=first[u];i;i=tree[i].next){v=tree[i].ar;if (!h[v]){h[v]=h[u]+1;up[v][0]=u;g[v][0]=tree[i].l;dfs(v);}} }
int lca(int x,int y){if (getfa(x)!=getfa(y)) return -1;int i,j,ans=1e9;if (h[y]>h[x]) swap(x,y);for (;h[x]>h[y];){for (i=0;h[up[x][i]]>=h[y];i++);i--;ans=min(ans,g[x][i]);x=up[x][i];}for (;x!=y;){for (i=1;up[x][i]!=up[y][i];i++);i--;ans=min(ans,min(g[x][i],g[y][i]));x=up[x][i];y=up[y][i];}return ans;}
int main() {scanf("%d%d",&n,&m);for (i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),road[i]=(info){x,y,z,0};sort(road+1,road+m+1,cmp);for (i=1;i<=n;i++) fa[i]=i;for (i=1;i<=m;i++){fx=getfa(road[i].fr);fy=getfa(road[i].ar);if (fx!=fy){fa[fx]=fy;tree[++num]=(info){road[i].fr,road[i].ar,road[i].l,first[road[i].fr]};first[road[i].fr]=num;tree[++num]=(info){road[i].ar,road[i].fr,road[i].l,first[road[i].ar]};first[road[i].ar]=num;}}for (i=1;i<=n;i++)if (!h[i]){h[i]=1;dfs(1);up[i][0]=i;g[i][0]=1e9; }for (i=1;i<=15;i++) for (j=1;j<=n;j++) {up[j][i]=up[up[j][i-1]][i-1];g[j][i]=min(g[j][i-1],g[up[j][i-1]][i-1]);} for (scanf("%d",&q);q;q--){scanf("%d%d",&x,&y);printf("%d\n",lca(x,y));}}

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