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 |
Re:upIn Reply To:why TLE?O(n^3)呀 Posted by:Chojin at 2008-05-01 10:32:48 #include<cstdio> #include<cstring> #include<cmath> #define maxn 128 #define maxint 0x7fffffff struct node{ double x,y; }; node pos[maxn]; int n,m; double g[maxn][maxn]; double G[maxn][maxn]; bool disable[maxn]; int pre[maxn]; bool visit[maxn]; double dist(node p1,node p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } void DFS(int v) { visit[v]=true; for(int i=1;i<=n;i++) if(g[v][i]>0 && visit[i]==false) DFS(i); } bool check(double g[][maxn],int n) { memset(visit,false,sizeof(visit)); DFS(1); for(int i=1;i<=n;i++) if(visit[i]==false) return false; return true; } int existCycle(double g[][maxn],int N,int pre[maxn]) { int i,j; for(i=2;i<=N;i++) { if(pre[i]==0) continue; j=i; j=pre[j]; while(j>0 && j!=i) { j=pre[j]; } if(j==i) return i; } return 0; } double Min(double a,double b) { return a<b?a:b; } double solve() { double res=0; int i,j; double min; int N=n; int u,x; for(;;) { memset(pre,0,sizeof(pre)); memset(disable,false,sizeof(disable)); for(i=2;i<=N;i++) { min=maxint; for(j=1;j<=N;j++) { if(g[j][i]>0 && min>g[j][i]) { min=g[j][i]; pre[i]=j; } } } if((u=existCycle(g,N,pre))==0) { break; } res+=g[pre[u]][u]; x=u; disable[x]=true; for(u=pre[x];u!=x;u=pre[u]) { res+=g[pre[u]][u]; disable[u]=true; } memset(G,0,sizeof(G)); u=x; for(i=1;i<=N;i++) { if(g[u][i]>0 && disable[i]==false) G[x][i]=g[u][i]; if(g[i][u]>0 && disable[i]==false) G[i][x]=g[i][u]-g[pre[u]][u]; } for(u=pre[x];u!=x;u=pre[u]) { for(i=1;i<=N;i++) { if(g[u][i]>0 && disable[i]==false) G[x][i]=Min(G[x][i],g[u][i]); if(g[i][u]>0 && disable[i]==false) G[i][x]=Min(G[i][x],g[i][u]-g[pre[u]][u]); } } for(i=1;i<=N;i++) for(j=1;j<=N;j++) if(disable[i]==false && disable[j]==false && g[i][j]>0) G[i][j]=g[i][j]; memset(g,0,sizeof(g)); for(i=1;i<=N;i++) for(j=1;j<=N;j++) g[i][j]=G[i][j]; } for(i=2;i<=N;i++) if(pre[i]>0) res+=g[pre[i]][i]; return res; } int main() { //freopen("f.txt","r",stdin); int i,x,y; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) scanf("%lf%lf",&pos[i].x,&pos[i].y); memset(g,0,sizeof(g)); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(x!=y) g[x][y]=dist(pos[x],pos[y]); } if(!check(g,n)) { printf("poor snoopy\n"); continue; } printf("%.2lf\n",solve()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator