?題意是給出一個不連通的圖，然后定義了一個直徑：聯通分量里最短距離最長的兩個點之間的距離。

?求將一個不連通的圖中的兩個連通分量連接，生成的這個新分量的直徑最小可以有多小，輸出這個新直徑。

做法是想用Floyd求出任意兩點之間的最短距離，然后求出每個點到未生成新圖之前的這個點所在分量的最遠的一個點的距離。然后枚舉聯通兩個不相連的兩個點，這兩個點的所在分量的最遠距離，加上這兩個點之間的距離，就是新生成的牧場的直徑。

題目保證一定會有未聯通的兩個分量：

但是：這道題的第7個測試點我就是死活過不去，然后把這個數據分析了一下發現，這個測試點里的所有點都聯通。

在此之前我還專門證明過，一個分量內部的直徑一定小于兩個分量相連之后新生成的分量的直徑。結果題目這種測試數據和題目描述不一致坑的我什么都不想說了。

我就是想問一下人與人之間基本的信任呢

/* ID: modengd1 PROG: cowtour LANG: C++ */ #include <iostream> #include <stdio.h> #include <memory.h> #include <math.h> #define INF 0xfffffff using namespace std; typedef pair<int,int> Coor; double longestdist[151]; double A[151][151]; Coor coor[151]; bool con[151][151]; int N; void Floyd() {//求任意間接聯通的兩點之間的最短路徑，并標記它們之間的間接聯通關系for(int k=0;k<N;k++){for(int i=0;i<N;i++){if(A[i][k]!=INF&&k!=i)for(int j=0;j<N;j++){if(A[k][j]!=INF&&k!=j){A[i][j]=min(A[i][j],A[i][k]+A[k][j]);con[i][j]=true;}}}} } double dis(Coor A,Coor B) {return sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second)); } void slove() {double ans=INF;//找到每個節點所在分量中離這個節點最遠的一個坐標的距離for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(con[i][j]){longestdist[i]=max(longestdist[i],A[i][j]);}}}//枚舉任意兩個不連通的點并且模擬將這兩個點聯通之后形成新牧場的直徑for(int i=0;i<N-1;i++){for(int j=1+i;j<N;j++){if(!con[i][j]){ans=min(ans,longestdist[i]+longestdist[j]+dis(coor[i],coor[j]));}}}for(int i=0;i<N;i++)//處理假如數據已經全部連通了怎么辦（題目強調一定有沒連通的兩個點，又碰見這種測試數據和題目描述不一樣的我也是醉了ans=max(longestdist[i],ans);printf("%.6lf\n",ans); } int main() {freopen("cowtour.in","r",stdin);freopen("cowtour.out","w",stdout);scanf("%d",&N);int a,b;char ch;for(int i=0;i<N;i++){scanf("%d%d",&a,&b);coor[i].first=a;coor[i].second=b;}getchar();for(int i=0;i<N;i++){for(int j=0;j<N;j++){scanf("%c",&ch);if(ch=='0')//判斷是否直接聯通并且初始化用來Floyd的A數組{con[i][j]=false;A[i][j]=INF;}else{con[i][j]=true;A[i][j]=dis(coor[i],coor[j]);}}getchar();con[i][i]=true;//自己到自己一定是聯通的且距離為0A[i][i]=0;}Floyd();slove();return 0; }

　　

轉載于:https://www.cnblogs.com/modengdubai/p/4786944.html

總結

以上是生活随笔為你收集整理的usaco Cow Tours的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。