https://www.luogu.com.cn/problem/P2872
数据范围不大,所以可以暴力处理图,然后用最小生成树
已经加进去的边不可能再加一次了,并查集会自动把他们筛掉
调试的时候一直不出答案,很离谱
最终发现是因为没有输入n和m。。。。。
然后数组开小了,改对了就没问题了
#include<bits/stdc++.h>
using namespace std;
#define in Read()
typedef long long ll;
#define int long long
int in{
int i=0,f=1; char ch=0;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') f=-1, ch=getchar();
while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
return i*f;
}
const int N=1e3+5;
int n,m,tot,fa[N],cnt;
double ans;
pair<int,int> d[N];
struct edge{
int u,v;
double w;
edge(){}
edge(int U,int V,double W){u=U, v=V, w=W;}
}e[N*N];
double dis(int u,int v){ return sqrt((d[u].first-d[v].first)*(d[u].first-d[v].first)+(d[u].second-d[v].second)*(d[u].second-d[v].second));}
bool cmp(const edge &a, const edge &b){ return a.w<b.w;}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
signed main(){
// freopen("1.in","r",stdin);
n=in,m=in;
for(int i=1;i<=n;++i){
int x=in,y=in;
d[i]=make_pair(x,y);
}
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i){
int u=get(in), v=get(in);
if(u==v) continue;
++tot;
fa[u]=v;
}
for(int u=1;u<=n;++u)
for(int v=u+1;v<=n;++v)
e[++cnt]=edge(u,v,dis(u,v));
// for(int i=1;i<=cnt;++i) printf("%d %d %.2lf\n",e[i].u,e[i].v,e[i].w);
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;++i){
int u=get(e[i].u),v=get(e[i].v);
if(u==v) continue;
++tot;
fa[u]=v;
ans+=e[i].w;
if(tot==n-1){
printf("%.2lf\n",ans);
return 0;
}
}
}
标签:ch,21,修路,int,ce,second,edge,long,first
From: https://www.cnblogs.com/antimony-51/p/16996668.html