当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 二分答案+图论 例题题解 c++

二分答案+图论 例题题解 c++

2020年10月25日  | 移动技术网IT编程  | 我要评论
题目：传送门首先这题的 最短路 不一定是最优解，因为题目说是路径上最长的一条边的值最小。所以改良一个 BFS 求最短路（不就是接近SPFA吗）结合二分答案，求出结果。AC代码：#include<bits/stdc++.h>using namespace std;#define MAXN 50010#define RI register intint end[MAXN],value[MAXN],nxt[MAXN],head[MAXN];int q[MAXN],n,m,s,t,fr

题目：传送门
首先这题的 最短路 不一定是最优解，因为题目说是路径上最长的一条边的值最小。
所以改良一个 BFS 求最短路（不就是接近SPFA吗）结合二分答案，求出结果。
AC代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
#define RI register int
int end[MAXN],value[MAXN],nxt[MAXN],head[MAXN];
int q[MAXN],n,m,s,t,front,last,r=-999,l;
bool vis[MAXN];
void init(){
	memset(nxt,-1,sizeof(nxt));
	memset(head,-1,sizeof(head));
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(RI i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		value[i*2]=c;
		end[i*2]=b;
		nxt[i*2]=head[a];
		head[a]=i*2;
		value[i*2+1]=c;
		end[i*2+1]=a;
		nxt[i*2+1]=head[b];
		head[b]=i*2+1;
		if(c>r)r=c;
	}
}
bool check(int x){
	memset(vis,0,sizeof(vis));
	front=last=1;
	q[1]=s;vis[s]=1;
	while(front<=last){
		int v=head[q[front]];
		while(v!=-1){
			if(!vis[end[v]]&&value[v]<=x){
				q[++last]=end[v];
				vis[end[v]]=1;
			}
			v=nxt[v];
		}
		front++;
	}
	return vis[t];
}
int main(){
	init();
	r++;l=1;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}else l=mid+1;
	}
	printf("%d",l);
	return 0;
}

我这次竟然没有用链式前向星 …

谢谢阅读

本文地址：https://blog.csdn.net/SB_zero_mark/article/details/109269984

您可能感兴趣的文章:

如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！

相关文章:

验证码：
最近更新的文章
推荐阅读
如何使用匿名上位机 如何使用匿名上位机
浅谈C++ 虚函数 浅谈C++ 虚函数
Api网关 Api网关
HDFS学习记录（数据单位的比较、读写流程） HDFS学习记录（数据单位的比较、读写流程）
大家感兴趣的文章
移动技术网