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<stdlib.h> #include<string.h> #include<math.h> #define maxn 105 #define INF 2000000000 double arr[maxn][maxn]; int n,m; int st,ed; struct node { double x; double y; }brr[105]; double zhuliu() { bool visited[maxn]; bool flag[maxn]; int pre[maxn]; double sum=0; int i,j,k; for(i=0;i<n;i++) { flag[i]=false; arr[i][i]=INF; } pre[0]=0; while(true) { for(i=1;i<n;i++) { if(flag[i]) continue; pre[i]=i; for(j=0;j<n;j++) if(!flag[j]&&arr[j][i]<arr[pre[i]][i]) pre[i]=j; if(pre[i]==i) return -1; } for(i=1;i<n;i++) { if(flag[i]) continue; for(j=0;j<n;j++) visited[j]=false; visited[0]=true; j=i; do { visited[j]=true; j=pre[j]; }while(!visited[j]); if(!j) continue; i=j; do { sum+=arr[pre[j]][j]; j=pre[j]; }while(j!=i); j=i; do { for(k=0;k<n;k++) if(!flag[k]&&arr[k][j]<INF&&k!=pre[j]) arr[k][j]-=arr[pre[j]][i]; j=pre[j]; }while(j!=i); for(j=0;j<n;j++) { if(j==i) continue; for(k=pre[i];k!=i;k=pre[k]) { if(arr[k][j]<arr[i][j]) arr[i][j]=arr[k][j]; if(arr[j][k]<arr[j][i]) arr[j][i]=arr[j][k]; } } for(j=pre[i];j!=i;j=pre[j]) flag[j]=true; break; } if(i==n) { for(i=1;i<n;i++) if(!flag[i]) sum+=arr[pre[i]][i]; break; } } return sum; } int main() { while(scanf("%d %d",&n,&m)!=EOF) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) arr[i][j]=INF; for(int i=0;i<n;i++) scanf("%lf %lf",&brr[i].x,&brr[i].y); for(int i=0;i<m;i++) { scanf("%d %d",&st,&ed); st--; ed--; arr[st][ed]=sqrt((brr[st].x-brr[ed].x)*(brr[st].x-brr[ed].x)+(brr[st].y-brr[ed].y)*(brr[st].x-brr[ed].x)); } double ans=zhuliu(); if(ans==-1) printf("poor snoopy\n"); else printf("%.2lf\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator