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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//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]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 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());
}
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%