正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1522

---

題目大意

有n個點，連接任意兩個不同聯通塊上的點，使這個新的聯通塊之間最遠的兩個點的距離最遠。

---

解題思路

先Flody$O(n^3)$計算兩兩之間的距離
然后計算出每個點最遠的點的距離，之后對于枚舉兩個不同聯通塊中的點，那么可能產生的新的權值就是兩個個點的最遠的點距離加上這兩個點之間的距離，但是還要和合并前聯通塊中最遠的點的距離比較

---

code

// luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #define N 160 #define pows(x) x*x using namespace std; int n,inx[N],tot; double x[N],y[N],a[N][N],d[N],md[N],mins; char c; double const_dis(int i,int j) {return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } void dfs(int x)//分聯通塊 {inx[x]=tot;for(int i=1;i<=n;i++)if(!inx[i]&&a[x][i]!=2147483647)dfs(i); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>c;if(c=='1')a[i][j]=const_dis(i,j);else if(i!=j) a[i][j]=2147483647;}for(int i=1;i<=n;i++)if(!inx[i]) tot++,dfs(i);for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];//計算最短路for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(a[i][j]!=2147483647)md[i]=max(md[i],a[i][j]);//每個點的最遠距離d[inx[i]]=max(d[inx[i]],md[i]);//每個聯通塊最遠距離}mins=2147483647;for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)if(inx[i]!=inx[j])mins=min(mins,max(md[i]+md[j]+const_dis(i,j),max(d[inx[i]],d[inx[j]])));printf("%.6lf",mins); }

總結

以上是生活随笔為你收集整理的USACO2.4のP1522-牛的旅行(Cow Tours)【最短路Flody】的全部內容，希望文章能夠幫你解決所遇到的問題。

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