洛谷 P2872 [USACO07DEC]Building Roads SFiveneves的博客-

P2872 [USACO07DEC]Building Roads S

题目链接-P2872 [USACO07DEC]Building Roads S



解题思路

$Kruskal$

Kruskal板子题

• 枚举每一个点，求出两点间的距离，连边，用结构体储存，并按照升序排序
• 对于之前已有道路，因为边权为零，所以可以直接将其合并，不用进行存储
• 其它的就都是
  $Kruskal$

  Kruskal的板子了，如果有不会并查集的，建议先去学习并查集再来看这道题

• 具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long #define lowbit(x) (x &(-x)) #define endl 'n' using namespace std; const int INF=0x3f3f3f3f; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; const double PI=acos(-1.0); const double e=exp(1.0); const double eps=1e-10; const int M=1e9+7; const int N=1e6+10; typedef long long ll; typedef pair<int,int> PII; typedef unsigned long long ull; int cnt,f[1010]; double x[1010],y[1010],ans; struct node{ int u,v; double w; }edge[N];//存边 int find(int x){//找爸爸 return f[x]==x?x:f[x]=find(f[x]); } void merge(int x,int y){//合并  f[find(x)]=find(y); } void add(int i,int j){//用结构体储存边  cnt++;//记录边的条数  edge[cnt].u=i;  edge[cnt].v=j;  edge[cnt].w=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));//计算两点间距离 } bool cmp(node x,node y){//按照道路长度排序 return x.w<y.w; } signed main(){  ios::sync_with_stdio(false);  cin.tie(0);cout.tie(0); int n,m;  cin>>n>>m; for(int i=1;i<=n;i++)   f[i]=i;//一定要初始化！！！ for(int i=1;i<=n;i++)   cin>>x[i]>>y[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i!=j) add(i,j);//储存边 } } for(int i=1;i<=m;i++){ int c,d;   cin>>c>>d; merge(c,d);//已有道路直接合并 } sort(edge+1,edge+cnt+1,cmp);//记住是cnt，不要顺手打成n //因为这个点找了好久的bug≡(▔﹏▔)≡ for(int i=1;i<=cnt;i++){ if(find(edge[i].u)!=find(edge[i].v)){//如果当前道路没有连通 merge(edge[i].u,edge[i].v);//合并    ans+=edge[i].w;//加上这条道路的长度 } }  cout<<fixed<<setprecision(2)<<ans<<endl; return 0; }