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> int n,graph[100][100],dis[100],use[100]; void prim(){ int i,j,k,m,min; int sum=0; for(i=1;i<=n;i++){ dis[i]=graph[1][i]; use[i]=1; } use[1]=0; for(i=1;i<n;i++){ min=0x7fffffff; for(k=2;k<=n;k++) if(use[k]&&dis[k]<min){ min=dis[k]; m=k; } sum+=min; use[m]=0; for(j=1;j<=n;j++) if(use[j]&&graph[m][j]!=0&&dis[j]>graph[m][j]) dis[j]=graph[m][j]; } printf("%d\n",sum); } int main(){ while(scanf("%d",&n)!=EOF){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&graph[i][j]); prim(); } return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator