Input
Output
1 #include<iostream> 2 #include<string.h> 3 #include<cmath> 4 #include<iomanip> 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 //kruskal 8 9 int n,p; 10 11 struct edge 12 { 13 double x; 14 double y; 15 }e[220]; 16 17 double addedge[4001]; 18 int f[4001]; 19 double pre[4001]; 20 21 double cmp1(double x,double y) 22 { 23 return x<y; 24 } 25 26 double d(double x1,double y1,double x2,double y2) 27 { 28 return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); 29 } 30 31 void init() 32 { 33 for(int i=1;i<p;i++) 34 f[i]=i; 35 return ; 36 } 37 38 int getf(int x) 39 { 40 if(f[x]==x) 41 return x; 42 return getf[f[x]]; 43 } 44 45 int merge(int x,int y) 46 { 47 int t1=merge(x); 48 int t2=merge(y); 49 if(t1!=t2) 50 { 51 f[t2]=t1; 52 return 1; 53 } 54 return 0; 55 } 56 57 int main() 58 { 59 std::ios::sync_with_stdio(false); 60 cin.tie(0); 61 cout.tie(0); 62 63 while(cin>>n) 64 { 65 if(n==0) 66 break; 67 memset(e,0,sizeof(e)); 68 memset(addedge,0,sizeof(addedge)); 69 memset(f,0,sizeof(f)); 70 for(int i=0;i<n;i++) 71 cout<<e[i].x<<e[i].y; 72 p=1;//p条边 73 for(int i=0;i<n;i++) 74 { 75 for(int j=i+1;j<n;j++) 76 { 77 addedge[p++]=d(e[i].x,e[i].y,e[j].x,e[j].y); 78 } 79 } 80 sort(addedge+1,addedge+p+1,cmp1); 81 82 init(); 83 int minmaxx=-inf; 84 int countt=0; 85 int q=0; 86 for(int i=1;i<p;i++) 87 { 88 for(int j=i+1;j<p;j++) 89 { 90 if(merge(addedge[i],addedge[j])==1)//说明还未连通 91 { 92 countt++; 93 pre[q++]= 94 minmaxx=max(minmaxx,) 95 96 97 } 98 if(countt==p-2) 99 break; 100 } 101 102 } 103 104 105 106 107 int tt=1; 108 cout<<"Scenario #"<<tt++<<endl; 109 cout<<"Frog Distance = "; 110 cout<<setiosflags(ios::fixed)<<setprecision(3)<<dis<<endl; 111 } 112 return 0; 113 }
AC的是用那个五行代码过的:
1 #include<iostream> 2 #include<string.h> 3 #include<cmath> 4 #include<iomanip> 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 8 //点点之间的距离floyd 9 //找a-b所有路径中最大步数里面最小的 10 struct edge 11 { 12 // double x; 13 // double y; 14 int x; 15 int y; 16 } e[220]; 17 18 double a[220][220]; 19 int n; 20 21 double d(int x1,int y1,int x2,int y2) 22 { 23 return sqrt(((x2-x1)*(x2-x1)*1.0+(y2-y1)*(y2-y1)*1.0)*1.0); 24 } 25 26 void init() 27 { 28 for(int i=1;i<=n;i++) 29 { 30 for(int j=1;j<=n;j++) 31 { 32 if(i==j) 33 a[i][j]=0; 34 else 35 a[i][j]=inf; 36 } 37 } 38 } 39 40 int main() 41 { 42 std::ios::sync_with_stdio(false); 43 cin.tie(0); 44 cout.tie(0); 45 int tt=1; 46 while(cin>>n) 47 { 48 if(n==0) 49 break; 50 memset(e,0,sizeof(e)); 51 memset(a,0,sizeof(a)); 52 init(); 53 for(int i=1; i<=n; i++)//n个顶点 54 cin>>e[i].x>>e[i].y; 55 56 // p=1;//p条边 57 58 for(int i=1; i<=n; i++) 59 { 60 for(int j=i+1; j<=n; j++) 61 { 62 // addedge[p++]=d(e[i].x,e[i].y,e[j].x,e[j].y); 63 64 double dd=d(e[i].x,e[i].y,e[j].x,e[j].y); 65 if(a[i][j]>dd||a[j][i]>dd) 66 { 67 a[j][i]=a[i][j]=dd; 68 } 69 } 70 } 71 // sort(addedge+1,addedge+p+1,cmp1); 72 for(int k=1;k<=n;k++) 73 { 74 for(int i=1;i<=n;i++) 75 { 76 for(int j=1;j<=n;j++) 77 { 78 //if(a[i][j]a[i][k]+a[k][j]) 79 a[i][j]=min(a[i][j],max(a[i][k],a[k][j])); 80 } 81 } 82 } 83 double dis=a[1][2]; 84 cout<<"Scenario #"<<tt++<<endl; 85 cout<<"Frog Distance = "; 86 cout<<setiosflags(ios::fixed)<<setprecision(3)<<dis<<endl<<endl; 87 } 88 return 0; 89 }
POJ-2253-Frogger-/Floyd-Warshall/
原文:https://www.cnblogs.com/OFSHK/p/11269432.html