| ||||||||||
| 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