图论边权最小值最大或者最大值最小

题目大多数都是给你一张图让你求其中两点见所有通路上边权最小值最大或者最大值最小的值
首先我们分析直接暴力去做那是肯定不可以的，数据一多就会T如果给定一张图的话可以用堆优化的dij能保证NlogN复杂度
边权最小值最大
我们分析一下最初的dij+堆优化的思路就是从终点开始，小根堆维护当前最小的dis然后用它去递推下面的dis答到最优更新的目的。
也就是dis[当前点]=min(dis[当前点],dis[之前的点]+边权值)
这里我们也是那种递推的思想
f[当前点]=min(f[当前点],max(边权值,f[之前的点]))
这个递推式实际上有点最大连续子区间的感觉

//poj 2253(1~2之间所有路径上边权值最大的最小值)
#include <cstdio>
#include <queue>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll cnt,bk[305],ree;
double f[305];
struct node
{
	double v;
	ll id;
	bool operator<(const node& a) const 
	{
		return v>a.v;
	}
};
pair<double,double> a[200005];
double dis(int x,int y)
{
	double x1=a[x].first,y1=a[x].second,x2=a[y].first,y2=a[y].second;
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
priority_queue<node> q;
int main()
{
	int n;
	while(~scanf("%d",&n)&&n)
	{
		for(int i=1;i<=n;i++)
		scanf("%lf%lf",&a[i].first,&a[i].second),bk[i]=0,f[i]=1<<30;
		f[1]=0;
		node re;
		re.v=0.0,re.id=1;
		q.push(re);
		while(q.size())
		{
			node jk=q.top();
			q.pop();
			if(bk[jk.id]) continue;
			bk[jk.id]=1;
			for(int i=1;i<=n;i++)
			if(i!=jk.id&&max(f[jk.id],dis(jk.id,i))<f[i])
			{
				f[i]=max(f[jk.id],dis(jk.id,i));
				re.v=f[i],re.id=i;
				q.push(re);
			}
		}
		printf("Scenario #%lld\nFrog Distance = %.3lf\n\n",++ree,f[2]);
	}
}

// poj 1797(1-n所有路径上边权值最小值最大注意要用大根堆)  
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int head[1000005],bk[1000005],cnt,n,m,f[1000005];
struct edge
{
	int to,w,nxt;
}e[1000005];
struct node
{
	int v,id;
	node(int x,int y):v(x),id(y){};
	bool operator<(const node& a) const
	{
		return v<a.v;
	}
};
void add(int x,int y,int z)
{
	e[++cnt].to=y;e[cnt].w=z;e[cnt].nxt=head[x];head[x]=cnt;
}
int dij()
{
	for(int i=1;i<=n;i++) f[i]=bk[i]=0;
	f[1]=1<<30;
	priority_queue<node> q;
	q.push(node(0,1));
	while(q.size())
	{
		node jk=q.top();
		q.pop();
		if(bk[jk.id]) continue;
		bk[jk.id]=1;
		for(int i=head[jk.id];i;i=e[i].nxt)
		if(min(f[jk.id],e[i].w)>f[e[i].to])
		{
			f[e[i].to]=min(f[jk.id],e[i].w);
			q.push(node(f[e[i].to],e[i].to));
		}
	}
	return f[n];
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		int x,y,z;
		scanf("%d%d",&n,&m);
		cnt=0;
		memset(head,0,sizeof(head));
		while(m--)
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		printf("Scenario #%d:\n%d\n\n",k,dij());
	}
}