题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1626
题意:略。
思路:最小生成树变形,我们把已经建好道路的边权设为0然后跑下最小生成树就可以了。
#include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #define MOD 1000000007 #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define Key_Value ch[ch[root][1]][0] #define DBN1(a) cerr<<#a<<"="<<(a)<<"\n" #define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n" #define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n" #define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n" #define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n" #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n" #define clr(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1000+5; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);} template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;} template<typename T> inline T read(T&x){ x=0;int _f=0;char ch=getchar(); while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x=_f?-x:x; } struct Edge{ int u,v; double len; Edge(int _,int __,double ___):u(_),v(__),len(___){} friend bool operator<(const Edge&a,const Edge&b){ return a.len<b.len; } }; int n,m; vector<Edge>edges; int fa[maxn]; double x[maxn],y[maxn]; double cnt(int a,int b){return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));} int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);} int main(){ read(n),read(m); for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]),fa[i]=i; for (int i=1;i<=n;i++){ for (int j=1;j<i;j++){ double len=cnt(i,j); edges.push_back(Edge(i,j,len)); } } for (int i=1;i<=m;i++){ int u,v;read(u),read(v); edges.push_back(Edge(u,v,0)); } sort(edges.begin(),edges.end()); int c=0; double ans=0; for (int i=0;i<(int)edges.size();i++){ Edge&e=edges[i]; int u=e.u,v=e.v; int tx=Find(u),ty=Find(v); if (tx!=ty){ fa[tx]=ty; ans+=e.len; if (++c>=n-1) break; } } printf("%.2lf\n",ans); return 0; }