真的不是我故意不打回车
by Taduro @ 2018-04-27 18:24:39
我的代码
```
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
struct point{
int x; int y; double v;
}w[1000001];
const int gun=1000000000;
using namespace std;
int fa[1001],i,j,n,m,k,x[1001],y[1001],p,a,b;
double t;
int cmp(const point &a,const point &b)
{
if (a.v<b.v) return 1;
else return 0;
}
int find(int x){
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
double dist(int x,int x1,int y,int y1){
return sqrt((double)(x-x1)*(x-x1)+(double)(y-y1)*(y-y1));
}
void unionn(int x,int y){
int a=find(x),b=find(y);
if (a!=b) fa[a]=b;
}
int main(){
cin>>n>>m;
for (i=1; i<=n; i++)
cin>>x[i]>>y[i];
for (i=1; i<=n; i++)
for (j=1+i; j<=n; j++){
w[++p].v=dist(x[i],x[j],y[i],y[j]);
w[p].x=i; w[p].y=j;
}
for (i=1; i<=m; i++){
cin>>a>>b;
w[++p].x=a; w[p].y=b; w[p].v=0;
}
sort(w+1,w+p+1,cmp);
for (i=1; i<=n; i++) fa[i]=i;
for (i=1; i<=n-1; i++){
if (find(w[i].x)!=find(w[i].y)){
unionn(w[i].x,w[i].y);
t+=w[i].v;
}
}
printf("%.2llf",t);
return 0;
}```
by Taduro @ 2018-04-27 18:26:00
@[多弗桃](/space/show?uid=63661) 复制到记事本里就行了
by Victory_Defeat @ 2018-04-27 18:27:52
@[地表最弱蒟蒻](/space/show?uid=70592) 我就是用记事本下的啊
by Taduro @ 2018-04-27 18:31:07
用写字板打开
by Siyuan @ 2018-04-27 18:33:45
@[siyuan](/space/show?uid=49725) 先不说这个，可我自己测试样例都过了，请问程序有什么问题吗
by Taduro @ 2018-04-27 18:35:50
```#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
struct point{
int x; int y; double v;
}w[1000001];
using namespace std;
long long fa[1001],i,j,n,m,k,x[1001],y[1001],p,a,b;
double t;
int cmp(const point &a,const point &b)
{
if (a.v<b.v) return 1;
else return 0;
}
int find(int x){
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
double dist(int x,int x1,int y,int y1){
return sqrt((double)(x-x1)*(x-x1)+(double)(y-y1)*(y-y1));
}
void unionn(int x,int y){
int a=find(x),b=find(y);
if (a!=b) fa[a]=b;
}
int main(){
cin>>n>>m;
for (i=1; i<=n; i++)
cin>>x[i]>>y[i];
for (i=1; i<=n; i++)
for (j=1+i; j<=n; j++){
w[++p].v=dist(x[i],x[j],y[i],y[j]);
w[p].x=i; w[p].y=j;
}
sort(w+1,w+p+1,cmp);
for (i=1; i<=n; i++) fa[i]=i;
for (i=1; i<=m; i++){
cin>>a>>b;
unionn(a,b);
}
for (i=1; i<=n-1-m; i++){
if (find(w[i].x)!=find(w[i].y)){
unionn(w[i].x,w[i].y);
t+=w[i].v;
}
}
printf("%.2llf",t);
return 0;
}```
by Taduro @ 2018-04-27 18:54:21
优化了一下
by Taduro @ 2018-04-27 18:54:36
emmm……这不是最小生成树模板么
by Victory_Defeat @ 2018-04-27 19:12:22
@[地表最弱蒟蒻](/space/show?uid=70592) 我只会打模板啊
by Taduro @ 2018-04-28 10:56:21