Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:up

Posted by Chojin at 2008-05-01 16:06:29 on Problem 3164
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator