當(dāng)前位置：首頁(yè) > 人文社科 > 生活经验 >内容正文

生活经验

P2245 星际导航

發(fā)布時(shí)間：2023/11/27 生活经验 20 豆豆

生活随笔收集整理的這篇文章主要介紹了 P2245 星际导航小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

題目描述

sideman 做好了回到Gliese星球的硬件準(zhǔn)備，但是sideman的導(dǎo)航系統(tǒng)還沒有完全設(shè)計(jì)好。為了方便起見，

我們可以認(rèn)為宇宙是一張有N 個(gè)頂點(diǎn)和M 條邊的帶權(quán)無向圖，頂點(diǎn)表示各個(gè)星系，兩個(gè)星系之間有邊就表示兩個(gè)星系之間可以直航，

而邊權(quán)則是航行的危險(xiǎn)程度。

sideman 現(xiàn)在想把危險(xiǎn)程度降到最小，具體地來說，就是對(duì)于若干個(gè)詢問(A,B)，sideman 想知道從頂點(diǎn)A

航行到頂點(diǎn)B 所經(jīng)過的最危險(xiǎn)的邊的危險(xiǎn)程度值最小可能是多少。作為 sideman的同學(xué)，你們要幫助sideman

返回家園，兼享受安全美妙的宇宙航行。所以這個(gè)任務(wù)就交給你了。

輸入輸出格式

輸入格式：

第一行包含兩個(gè)正整數(shù)N和M，表示點(diǎn)數(shù)和邊數(shù)。

之后M行，每行三個(gè)整數(shù)A，B和L，表示頂點(diǎn)A和B之間有一條邊長(zhǎng)為L(zhǎng)的邊。頂點(diǎn)從1開始標(biāo)號(hào)。

下面一行包含一個(gè)正整數(shù)Q，表示詢問的數(shù)目。

之后Q行，每行兩個(gè)整數(shù) A和B，表示詢問A和B之間最危險(xiǎn)的邊危險(xiǎn)程度的可能最小值。

輸出格式：

對(duì)于每個(gè)詢問，在單獨(dú)的一行內(nèi)輸出結(jié)果。如果兩個(gè)頂點(diǎn)之間不可達(dá)，輸出impossible。

輸入輸出樣例

輸入樣例#1：?

輸出樣例#1：?

5
4
5

說明

對(duì)于 40%的數(shù)據(jù)，滿足 N≤1000,M≤3000,Q≤1000

對(duì)于 80%的數(shù)據(jù)，滿足 N≤10000,M≤10⁵,Q≤1000

對(duì)于 100% 的數(shù)據(jù)，滿足 N≤10⁵,M≤3×10⁵,Q≤10⁵，L≤10⁹，數(shù)據(jù)不保證沒有重邊和自環(huán)。

代碼

kruskal重構(gòu)樹裸題，做法同貨車運(yùn)輸

最危險(xiǎn)的邊危險(xiǎn)程度的可能最小值，也就是最大值最小

我們邊權(quán)按升序排序，val[lca(x,y)]即為答案

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+100,maxm=200000+100,md=20+5;
int head[maxn],val[maxn],f[maxn],dep[maxn],lg[maxn]; 
int ff[maxn][md];
int size=0,cnt=0;
struct tree
{int to,next;
}e[maxm<<1];
struct edge
{int u,v,val;
}E[maxm<<1];
int n,m;
void init()
{for(int i=1;i<=n;i++)f[i]=i;
}
int find(int x)
{return f[x]==x?x:f[x]=find(f[x]);
}
void addedge(int u,int v)
{e[++size].to=v;e[size].next=head[u];head[u]=size;
}
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<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
bool cmp(const edge&a,const edge&b)
{return a.val>b.val;
}
void kruskal()
{for(int i=1;i<=m;i++){int u=E[i].u,v=E[i].v;int fu=find(u),fv=find(v);if(fu!=fv){cnt++;f[cnt]=f[fu]=f[fv]=cnt;val[cnt]=E[i].val;addedge(cnt,fu);addedge(fu,cnt);addedge(fv,cnt);addedge(cnt,fv);}}
}
void dfs(int u,int fa)
{dep[u]=dep[fa]+1;ff[u][0]=fa;for(int i=1;i<=lg[dep[u]];i++)ff[u][i]=ff[ff[u][i-1]][i-1];for(int i=head[u];i;i=e[i].next){int to=e[i].to;if(to==fa)continue;dfs(to,u);}
}
int lca(int x,int y)
{if(dep[x]<dep[y])swap(x,y);while(dep[x]>dep[y])x=ff[x][lg[dep[x]-dep[y]]];if(x==y)return x;for(int i=lg[dep[x]];i>=0;i--)if(ff[x][i]!=ff[y][i])x=ff[x][i],y=ff[y][i];return ff[x][0];
}
int main()
{n=read(),m=read();cnt=n;init();for(int i=1;i<=m;i++)E[i].u=read(),E[i].v=read(),E[i].val=read();sort(E+1,E+1+m,cmp);kruskal();for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);for(int i=1;i<=cnt;i++)if(!dep[i])dfs(find(i),0); int k=read();for(int i=1;i<=k;i++){int x=read(),y=read();if(find(x)!=find(y))printf("-1\n");else printf("%d\n",val[lca(x,y)]);}return 0;
}