网站建设毕业设计选题,双色调网站,辽宁建设工程信息网企业人员调动,进qq空间上面没有网站正题
题目链接#xff1a; https://www.luogu.org/problemnew/show/P1967 大意
一个无向图#xff0c;每个边有个权值#xff0c;若干个询问#xff0c;求两个点之间的一条最短路是这条最短路上的最小权值最大。 解题思路
首先我们发现其实每两个点之间留一条路径就好了…正题
题目链接 https://www.luogu.org/problemnew/show/P1967 大意
一个无向图每个边有个权值若干个询问求两个点之间的一条最短路是这条最短路上的最小权值最大。 解题思路
首先我们发现其实每两个点之间留一条路径就好了。 然后我们会发现如果x到y的路上最小权值最大是w那么如果z有一条边连向x那么z到y的路上最小权值就有可能是w。 其实我们可以去掉一些边只留需要的最大的边就好了这么一看其实就是留下最大生成树。那么在树上进行求LCA然后在之前类似RMQ一样预处理一下就可以求两个点之间的最小权值了。 代码
#includecstdio
#includequeue
#includealgorithm
#includecmath
using namespace std;
queueint dl;
struct line{int to,next,w,from;
};//边
struct pic{line a[100001];int ls[10001],tot;void addl(int x,int y,int w){a[tot].toy;a[tot].fromx;a[tot].nextls[x];a[tot].ww;ls[x]tot;}
}p,tree;//图
int t,n,m,q,x,y,z,s;
int father[10001],f[10001][31],dis[10001][31],dep[10001];
int find(int x)//并查集-kruskal
{return father[x]x?x:father[x]find(father[x]);}
bool cmp(line x,line y)//排序-kruskal
{return x.wy.w;}
void bfs(int open)//广搜预处理-树上倍增
{dl.push(open);dep[open]1;while (dl.size()){int xdl.front();dl.pop();for (int itree.ls[x];i;itree.a[i].next){int ytree.a[i].to;if (dep[y]) continue;dl.push(y);f[y][0]x;dep[y]dep[x]1;dis[y][0]tree.a[i].w;}}
}
int LCA(int x,int y)//树上倍增
{int ans2147483647;if (dep[x]dep[y]) swap(x,y);for (int it;i0;i--)if (dep[f[y][i]]dep[x])ansmin(ans,dis[y][i]),yf[y][i];if (xy) return ans;for (int it;i0;i--)if (f[y][i]!f[x][i]) {ansmin(ans,min(dis[x][i],dis[y][i]));//统计xf[x][i];yf[y][i];}ansmin(ans,min(dis[x][0],dis[y][0]));return ans;
}
int main()
{scanf(%d%d,n,m);for (int i1;im;i){scanf(%d%d%d,x,y,z);p.addl(x,y,z);p.addl(y,x,z);}sort(p.a1,p.a1p.tot,cmp);for (int i1;in;i)father[i]i;for (int i1;ip.tot;i){if (find(p.a[i].to)!find(p.a[i].from)){s;tree.addl(p.a[i].to,p.a[i].from,p.a[i].w);tree.addl(p.a[i].from,p.a[i].to,p.a[i].w);father[find(p.a[i].to)]find(p.a[i].from);if (sn) break;}}//kruskalt(int)(log(n)/log(2))1;for (int i1;in;i)if (!dep[i]) {dis[i][0]2147483647;bfs(i);//广搜预处理}for (int j1;jt;j){for (int i1;in;i){f[i][j]f[f[i][j-1]][j-1];dis[i][j]min(dis[i][j-1],dis[f[i][j-1]][j-1]);}}//计算树上倍增与统计路径最小值的预处理scanf(%d,q);for (int i1;iq;i){scanf(%d%d,x,y);if (find(x)!find(y))printf(-1\n);//不连通elseprintf(%d\n,LCA(x,y));//输出}
}
