| 记录编号 |
193636 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[USACO Dec07] 建造路径 |
最终得分 |
100 |
| 用户昵称 |
 forever |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.535 s |
| 提交时间 |
2015-10-15 06:23:37 |
内存使用 |
16.56 MiB |
显示代码纯文本
- #include<cstdio>
- #include<cmath>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- struct dd{
- int Begin,End;
- double juli;
- }jie[1000505];
- int jk,n,m,fa[1005],ai,bi,sum;
- double data,x[1005],y[1005];
- bool vis[1005][1005];
- int find(int x){
- if(fa[x]==x) return x;
- fa[x]=find(fa[x]);
- return fa[x];
- }
- double Dis(int xo,int yo){
- return sqrt((x[xo]-x[yo])*(x[xo]-x[yo])+(y[xo]-y[yo])*(y[xo]-y[yo]));
- }
- bool comp(const dd & a,const dd & b){
- return a.juli<b.juli;
- }
- int main(){
- freopen("roads.in","r",stdin);
- freopen("roads.out","w",stdout);
- int yu,lin;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i) {
- scanf("%lf%lf",&x[i],&y[i]); fa[i]=i;
- }
- for(int i=1;i<=m;++i) {
- scanf("%d%d",&ai,&bi);
- jie[++jk].Begin=ai; jie[jk].End=bi; jie[jk].juli=0;
- jie[++jk].Begin=bi; jie[jk].End=ai; jie[jk].juli=0;
- vis[ai][bi]=1;
- }
- for(int i=1;i<=n;++i)
- for(int j=1;j<i;++j){
- if(i!=j&&!vis[i][j]){
- double temp=Dis(i,j);
- jie[++jk].Begin=i; jie[jk].End=j; jie[jk].juli=temp;
- jie[++jk].Begin=j; jie[jk].End=i; jie[jk].juli=temp;
- vis[i][j]=1;
- }
- }
- sort(jie+1,jie+jk+1,comp);
- for(int i=1;i<=jk;++i){
- yu=find(jie[i].Begin); lin=find(lin=jie[i].End);
- if(yu!=lin) {
- fa[lin]=yu;
- data+=jie[i].juli;
- sum++;
- }
- if(sum==n-1) break;
- }
- printf("%.2lf",data);
- getchar();getchar();
- }