網線

Time Limit: 5000 MS Memory Limit: 32768 K Total Submit: 68(17 users) Total Accepted: 17(15 users) Rating:? Special Judge:?No

Description

? ?試設計一個網絡連接某個區域中的一些地點。給定這些地點所在的位置，網線的長度就是兩個地點的線段距離，假定，給定的網線可以直接或間接的連接該地區中的所有點，試為這個地區設計一個網絡系統，使得該地區所有地點都可以直接或間接的連接，并且使用網線長度最短。

Input

輸入一個數字n（n<1000），給出這n個點的位置（x,y），即坐標（0≤x＜1000，0≤y＜1000）。

Output

輸出網線的最短距離，保留小數點后四位。

Sample Input

1 1 1 2 0 0 1 1 3 0 0 0 1 1 1

Sample Output

0.0000 1.4142 2.0000

Author

彭文文@hrbust

N的數據范圍比較大，克魯斯卡算法會超時，即使路徑壓縮了，即使使用快排了，還是會超時，所以被逼無奈，只能用prim來做。

在計算過程中呢，我們需要考慮一個精度問題，我們如果在入圖的時候就使用double或者float來寫的話，很容易產生精度差，當然就會有wa的可能。

所以我們在計算過程中，入圖的時候用int，只有在生成樹的過程中加上sqrt（map【i】【j】）就行了，這個時候我們避免了精度差問題，也省略了很多不必要的*1.0之類的步驟。

AC代碼：

#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; #define inf 0x6ffffff struct zuobiao {int x,y; }a[1004]; int vis[1005];//用來表示這個點有沒有遍歷的到. int dis[1005]; int map[1005][1005]; int n; double sum; int diss(zuobiao a,zuobiao b) {return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } void prim() {int i,j,k,min;for(i=2;i<=n;i++)dis[i]=map[1][i];vis[1]=1;for(i=2;i<=n;i++)//經過N次遍歷一定能遍歷所有的點 也就是完成了最終目標.{min=inf;for(j=1;j<=n;j++){if(vis[j]==0 &&dis[j]<min){min=dis[j];k=j;}}if(min==inf)break;vis[k]=1;sum+=sqrt(1.0*min);//完成了一次權值加和.for(j=2;j<=n;j++){if(vis[j]==0 &&dis[j]>map[k][j])dis[j]=map[k][j];}//更新最優解.}} int main() {while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));memset(dis,0,sizeof(dis));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){map[i][j]=inf*1.0;}}for(int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);for(int j=1;j<i;j++){map[i][j]=map[j][i]=diss(a[i],a[j]);}}sum=0;prim();printf("%.4lf\n",sum);} }

總結

以上是生活随笔為你收集整理的hrbust 哈理工oj 网线【MST+Prim】的全部內容，希望文章能夠幫你解決所遇到的問題。

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