poj 2253 Frogger

xiaoxiao2021-02-28  19

题目来源:POJ 2253

简单题目分析: 求A到B所有路径中权值最大边的最小值。 思路: 贪心,其实就是Kruskal,从一个空图开始,逐渐向里面加入最小权值的边,直到A与B连通,则最后加入的边就是答案。其实很多题目都与最小生成树有关,尤其是权值的最值问题。 #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; int pre[205]; struct line //起点、终点及权值 { int src; int dest; double len; }temp[20005]; bool cmp(line a,line b) { return a.len<b.len; } int findRoot(int x) { while(x!=pre[x]) x=pre[x]; return x; } double getDis(int x1,int y1,int x2,int y2) //计算两点间距离 { return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int x[205]; //记录横坐标 int y[205]; //记录纵坐标 int main() { int n; int index=1; while( ~scanf("%d",&n) && n!=0 ) { int k=1; int i,j; for(i=1;i<=n;++i) { pre[i]=i; int a,b; scanf("%d %d",&a,&b); x[k]=a; y[k]=b; k++; } k=0; for(i=1;i<=n;++i) for(j=i+1;j<=n;++j) { temp[k].src=i; temp[k].dest=j; temp[k++].len=getDis(x[i],y[i],x[j],y[j]); } double ans=0; sort(temp,temp+k,cmp); for(i=0;i<k;++i) { pre[findRoot(temp[i].dest)]=findRoot(temp[i].src); if(findRoot(1)==findRoot(2)) //判断第一块石头和第二块石头是否连通 { ans=temp[i].len; break; } } printf("Scenario #%d\n",index++); printf("Frog Distance = %.3lf\n",ans); //这里有G++和C++的区别,在于double类型输出的区别 printf("\n"); } return 0; } ps:我发现很多时候题目对于我来说,最难的地方在于怎么存储题目中所给的数据,比如这道题就需要把点的坐标存储下来,采用两个数组分别存储横纵坐标。
转载请注明原文地址: https://www.6miu.com/read-250418.html

最新回复(0)