# Hdu1875 畅通工程再续

## MST模板题

Posted by yjjr's blog on March 11, 2019

# Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=106;
struct edge{int u,v;double w;}e[maxn*maxn];
struct node{int x,y;}a[maxn];
int n,tot,cnt,num,fa[maxn],T;double ans;
inline bool cmp(edge a,edge b){return a.w<b.w;}
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
inline double dis(int s,int t){return sqrt((a[s].x-a[t].x)*(a[s].x-a[t].x)+(a[s].y-a[t].y)*(a[s].y-a[t].y));}
void kruskal(){
sort(e+1,e+1+cnt,cmp);
rep(i,1,cnt){
int r1=find(e[i].u),r2=find(e[i].v);
if(r1!=r2){ans+=e[i].w;fa[r1]=r2;tot++;}
}
}
int main(){
while(T--){