一道比较困难的Floyd题目。
首先路径肯定都会算，就不说了。其次，Floyd也没有什么问题。
我们的策略是枚举两个不联通的点，把他们联通，求出新牧区的最小直径。
关键细节看代码
（如果有哪位dalao知道为什么要 if (i!=k && j!=k && i!=j) 麻烦您在评论中回复我）
|
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 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<queue> using namespace std; int colx[300]={0},coly[300]={0},nodenum; double dis[300][300],direc[300]={0}; char cache1; double ans=1e10,cache2; int main() { scanf("%d",&nodenum); for (int i=0;i<nodenum;i++) scanf("%d%d",&colx[i],&coly[i]); for (int i=0;i<nodenum;i++) { for (int j=0;j<nodenum;j++) { cin>>cache1; if (cache1=='0') dis[i][j]=1e10; else dis[j][i]=dis[i][j]=sqrt(pow(colx[i]-colx[j],2)+pow(coly[i]-coly[j],2)); } } for (int k=0;k<nodenum;k++) for (int i=0;i<nodenum;i++) for (int j=0;j<nodenum;j++) if (i!=k && j!=k && i!=j && dis[i][k]+dis[k][j]<dis[i][j] && dis[i][k]<1e10 && dis[k][j]<1e10) { dis[i][j]=dis[i][k]+dis[k][j]; } for (int i=0;i<nodenum;i++) for (int j=0;j<nodenum;j++) if (dis[i][j]<1e10 && dis[i][j]>direc[i]) direc[i]=dis[i][j]; for (int i=0;i<nodenum;i++) for (int j=0;j<nodenum;j++) if (dis[i][j]==1e10 && i!=j) { cache2=direc[i]+direc[j]+sqrt(pow(colx[i]-colx[j],2)+pow(coly[i]-coly[j],2)); if (cache2<ans) ans=cache2; } /*!!*/for (int i=0;i<nodenum;i++) if (direc[i]>ans) ans=direc[i]; //注意这一句，因为一个联通块内的direc值不等，所以有可能新牧取的最大直径（通过枚举ij得到）恰好是两个牧区中direfc最小的点（牧场）链接得到的。 //有可能没有其中一个小牧区的单点direc值大。 so？ 有必要计算正确的直径 printf("%.6lf\n",ans); return 0; } |