Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
哎,超时!!!!!!!#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; struct st { int x; int y; double dis; }edge[1010]; double x[1010],y[1010]; bool cmp(const st&a,const st&b) { return a.dis < b.dis; } double Kruskal(int v,int e) { int i,j,an1,an2; int set[1010]; for(i = 1;i <= v;i++) set[i] = i; int count = 1; double sum = 0; sort(edge + 1,edge + e +1,cmp); i = 1; while(count < v) { an1 = set[edge[i].x]; an2 = set[edge[i].y]; if(an1 != an2) { count++; sum += edge[i].dis; for(j = 1;j <= v;j++) if(set[j] == an2) set[j] =an1; } i++; } return sum; } int main() { int i,j,n,m,k,a,b,temp; scanf("%d%d",&n,&m); for(i = 1;i <= n;i++) scanf("%lf%lf",&x[i],&y[i]); k = 0; for(i = 1;i <n;i++) for(j = i+1;j <= n;j++) { edge[++k].x = i; edge[k].y = j; edge[k].dis = sqrt(double((y[j] - y[i])*(y[j] - y[i])) + double((x[j] - x[i])*(x[j] - x[i]))); } for(i = 1;i <= m;i++) { scanf("%d%d",&a,&b); if(a > b){temp = a;a = b; b = temp;} for(j = 1;j <= k;j++) { if(edge[j].x == a&&edge[j].y == b) edge[j].dis = 0; } } printf("%.2lf\n",Kruskal(n,k)); return 0; } /*Sample Input 4 1 1 1 3 1 2 3 4 3 1 4 Sample Output 4.00 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator