劍魚行動

ssl 1618

題目大意：

求一個平面直角坐標系中的最小生成樹

原題：

題目描述

給出N個點的坐標，對它們建立一個最小生成樹，代價就是連接它們的路徑的長度，現要求總長度最小。N的值在100以內，坐標值在[-10000,10000].結果保留二位小數

輸入樣例

5 0 0 0 1 1 1 1 0 0.5 0.5

輸出樣例

2.83

解題思路：

首先用勾股定理求出長度，然后用并查集來求最小生成樹

代碼：

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,w,xxx,yyy,dad[1005]; double ans; struct rec {int x,y;double l; }a[1000005]; struct recc {double xx,yy; }b[1005]; bool cmp(rec aa,rec bb) {return aa.l<bb.l;} int find(int dep){return dad[dep]==dep?dep:dad[dep]=find(dad[dep]);} //并查集 int main() {scanf("%d",&n);for (int i=1;i<=n;++i){dad[i]=i;scanf("%lf %lf",&b[i].xx,&b[i].yy);for (int j=1;j<i;++j){a[++w].x=i;a[w].y=j;a[w].l=sqrt((b[i].xx-b[j].xx)*(b[i].xx-b[j].xx)+(b[i].yy-b[j].yy)*(b[i].yy-b[j].yy));//勾股定理}}sort(a+1,a+1+w,cmp);for (int i=1;i<=w;++i)if (find(a[i].x)!=find(a[i].y)){xxx=find(a[i].x);//尋找根節點yyy=find(a[i].y);dad[min(xxx,yyy)]=max(xxx,yyy);//合并ans+=a[i].l;}printf("%.2lf",ans); }

總結

以上是生活随笔為你收集整理的【并查集】【图论】【最小生成树】剑鱼行动（ssl 1618）的全部內容，希望文章能夠幫你解決所遇到的問題。

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