算是比较裸的并查集了,已经有路的两个点之间建一条代价为0的边,路径长度计算两点之间的距离,做并查集就好咯。
#include#include #include #include #include using namespace std;#define Ldouble long double#define LL long longint n,m,tot;struct ahah{ int x,y; Ldouble dis;}a[2000006];LL fa[1006],_,__,cnt;Ldouble calc(Ldouble x1,Ldouble y1,Ldouble x2,Ldouble y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int find(int x){ return fa[x]==x?x:find(fa[x]);}bool cmp(ahah a,ahah b){ return a.dis