模板网页生成,谷歌外贸seo,随州百度网站建设,大连优化网站题目
给一个无向图#xff0c;要求从点1到点2的一条路#xff0c;要求这条路上的边的最大值尽量小。
输入输入
多组数据#xff0c;每个数据n1行#xff0c;分别是n和点的坐标 2 0 0 3 4 3 17 4 19 4 18 5 0
输出
这条路上的边的最大值 Scenario #1 Frog Di…题目
给一个无向图要求从点1到点2的一条路要求这条路上的边的最大值尽量小。
输入输入
多组数据每个数据n1行分别是n和点的坐标 2 0 0 3 4 3 17 4 19 4 18 5 0
输出
这条路上的边的最大值 Scenario #1 Frog Distance 5.000
Scenario #2 Frog Distance 1.414 解题思路
这道题老师放在最短路里害的我被坑了好久 就是求一个最小生成树然后求这个生成树中点一到点二的路上求一个最大值。这里用并查集。 代码
#includecstdio
#includeiostream
#includealgorithm
#includecmath
using namespace std;
struct woc{int head,tail;double w;
};
int n,ti,lt[40001],kk;
double xx[201],yy[201],maxs;
woc a[40001];
int find(int x)
{if (x!lt[x]) return lt[x]find(lt[x]);else return x;
}
bool cmp(woc x,woc y)
{return x.wy.w;
}
int main()
{while (true){ti;scanf(%d,n);if (n0) break; for (int i1;in;i){scanf(%lf%lf,xx[i],yy[i]);}kk0;for (int i1;in;i)for (int j1;jn;j){if (i!j) {a[kk].wsqrt(abs(xx[i]-xx[j])*abs(xx[i]-xx[j])abs(yy[i]-yy[j])*abs(yy[i]-yy[j]));//求距离a[kk].headi;a[kk].tailj;//记录线}lt[i]i;} sort(a1,akk1,cmp);//按权值排序maxs0;for (int i1;ikk;i){int fafind(a[i].head);int fbfind(a[i].tail);//寻找祖先if (fa!fb){if (fafb) lt[fa]fb;else lt[fb]fa;//给一个固定的值这里用最大的那个if (find(1)find(2)) {maxsa[i].w;break;}//如果已经把点1和点2连接了//(因为这里排了序所以是最小的)}}printf(Scenario #%d\nFrog Distance %.3lf\n\n,ti,maxs);//输出}
} 附上原题
Description 有一只叫做Freddy的青蛙坐在湖中央的一块石头上突然间他发现另一只青蛙她的名字是Fiona坐在另一颗石头上。他想要过去找她但是因为湖水很脏到处充满着游客的防晒油所以他决定用跳的而不要用游的。 不妙的是Fiona的石头离他的距离超出他所能跳的范围。因此Freddy考虑利用其它的一些石头当作中继站因此他就可以跳比较小的距离或许要跳许多次去找Fiona。要这样子连续的跳很明显的Freddy一次能跳的距离必须至少和这一串石头间的距离最大的距离一样。因此介于石头间的蛙跳距离frog distance人类也称之为minmax distance定义为要从Freddy所在的石头要跳到Fiona所在的石头的路径中最小必须要跳的距离。给你Freddy所在的石头、Fiona所在的石头以及湖中所有其它石头的坐标你的任务是算出介于Freddy和Fiona所在石头间的蛙跳距离。
Input 输入含有多组测试数据。每组测试资料的第一列有1个整数n代表石头的数目2 n 200。接下来的n列每列有2个整数xiyi0 xiyi 1000代表第i颗石头的坐标。其中第一颗为Freddy所在的石头第二颗为Fiona所在的石头其它的n-2颗石头上则是空的。 每组测试数据后有一空白列当n0时代表输入结束。请参考Sample Input。
Output 对每一组测试数据输出一列这是第几组测试数据以及一列蛙跳距离。 每组测试数据后亦输出一空白列。请参考Sample Output。
Sample Input 2 0 0 3 4 3 17 4 19 4 18 5 0
Sample Output Scenario #1 Frog Distance 5.000
Scenario #2 Frog Distance 1.414
