首页 > 代码库 > BZOJ 1626: [Usaco2007 Dec]Building Roads
BZOJ 1626: [Usaco2007 Dec]Building Roads
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1626
赤裸裸的最次生成树,已有的边赋为0就好了,我用了prim(因为不熟)
不过有个神坑点,算坐标中乘法会超出int范围,所以在里面也要转为double(当然不排除你一开始用的就是long long)
程序:
#include<iostream> #include<cstdio> #include<cmath> #define INF 2100000000.0 using namespace std; int n,m,x[2000],y[2000]; double ans,dis[2000],f[2000][2000]; bool vis[2000]; void prim() { for (int i=1;i<=n;i++) { dis[i]=INF; vis[i]=false; } dis[1]=0.0; for (;;) { int ch=0; double minx=INF; for (int i=1;i<=n;i++) if ((!vis[i])&&(dis[i]<minx)) { minx=dis[i]; ch=i; } if (ch==0) break; vis[ch]=true; ans+=dis[ch]; for (int i=1;i<=n;i++) dis[i]=min(dis[i],f[ch][i]); } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) { double sum=(double)sqrt((double)(x[i]-x[j])*(double)(x[i]-x[j])+(double)(y[i]-y[j])*(double)(y[i]-y[j])); f[i][j]=f[j][i]=sum; } for (int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); f[a][b]=f[b][a]=0.0; } prim(); printf("%.2lf\n",ans); return 0; }
BZOJ 1626: [Usaco2007 Dec]Building Roads
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。