题目连接
https://www.acwing.com/problem/content/description/4243/
http://poj.org/problem?id=2253
思路
思路一(最短路)
我们直接跑一个最短路就好,基本上所有的最短路都可以,然后注意的是我们在做松弛操作的时候,也就是判断是否应该加入我们的优先队列中的时候,我们做的不是一个加上这条边而是和这条边去一个max
,也就是如果我们当前正在对起点t
,终点j
做一个松弛操作,那么我们做的不是dis[j]=max(dis[j],dis[t]+w)
而是dis[j]=max(dis[t],w)
我们这样就能记录下最长边了,那么现在的dis[i]
表示的就是从1开始到i结束的最长边的长度,而不是累计长度
思路二(最小生成树)
其实你发现没有,我们这里要求的问题其实就是让这个图联通的最大长度,那么这不就是最小生成树吗,我们对边进行排序,排完序后我们开始将边不断地加入集合中,最后让这个图联通的这个边自然就是整个连通图的最长距离了,所以我们可以直接通过最小生成树来解决这个问题
代码
最短路代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<int,int>
const int N = 2e2+10;
int dis[N],n;
struct Point{
int x,y;
}V[N];
struct Node{
int v,w;
};
vector<Node> E[N];
bool vis[N];
void DJ(){
priority_queue<PII,vector<PII>,greater<PII> > que;
que.push({0,1});
dis[1] = 0;
while(!que.empty()){
int w = que.top().first;
int t = que.top().second;
que.pop();
if(vis[t]) continue;
vis[t] = true;
for(int i = 0,l = E[t].size(); i < l; ++i) {
int j = E[t][i].v;
int k = E[t][i].w;
if(dis[j] > max(dis[t],k)){
dis[j] = max(dis[t],k);
que.push({dis[j],j});
}
}
}
}
inline int get_len(Point a,Point b){
return (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y);
}
void init(){
for(int i = 1;i <= n; ++i) E[i].clear(),dis[i] = 0x3f3f3f3f,vis[i] = false;
}
int main()
{
int t = 1;
while(cin>>n,n){
init();
for(int i = 1;i <= n; ++i) cin>>V[i].x>>V[i].y;
for(int i = 1;i <= n; ++i)
for(int j = i + 1;j <= n; ++j){
int w = get_len(V[i],V[j]);
E[i].push_back({j,w});
E[j].push_back({i,w});
}
DJ();
cout<<"Scenario #"<<t<<endl;
cout<<"Frog Distance = "<<fixed<<setprecision(3) <<(double)sqrt((double)dis[2])<<endl;
cout<<endl;
t++;
}
}
最小生成树
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int N = 200+10;
int fa[N * N];
int find(int x) {
while(x!=fa[x]) x = fa[x];
return x;
}
void merge(int a,int b) {
a = find(a);
b = find(b);
fa[b] = a;
}
struct Node {
double x,y;
}a[N];
struct edge {
int u,v;
double len;
};
bool cmp(edge A,edge B) {
return A.len < B.len;
}
vector<edge> V;
void init() {
for(int i = 1,len = N * N;i < len; ++i) {
fa[i] = i;
}
V.clear();
}
double get_len(int i,int j) {
return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
}
int main()
{
int cnt = 1;
int n;
while(~scanf("%d",&n)&&n) {
init();
for(int i = 1;i <= n; ++i) {
scanf("%lf%lf",&a[i].x,&a[i].y);
}
for(int i = 1;i <= n; ++i) {
for(int j = 1;j < i; ++j) {
double temp = get_len(i,j);
V.push_back({i,j,temp});
V.push_back({j,i,temp});
}
}
sort(V.begin(),V.end(),cmp);
for(int i = 0,len = V.size();i < len; ++i) {
edge E = V[i];
int l = E.u,r = E.v;
l = find(l),r = find(r);
if(l != r) {
fa[r] = l;
}
if(find(1) == find(2)) {
printf("Scenario #%d\n",cnt++);
printf("Frog Distance = %.3lf\n\n",E.len);
break;
}
}
}
return 0;
}
看懂了,真棒!😊
最小生成树,真的牛逼
生成树太顶了
find(1) == find(2)是什么意思啊
话说感觉这个可以直接二分答案呀
是可以二分,数据范围很小你二分跑Floyd都行,或者二分BFS咋搞都行