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

哪位大牛帮忙看看哪里错了呀,WA到死了哦,还发现不了问题!谢谢各位了

Posted by wangfengbo at 2008-08-26 21:59:35 on Problem 2536
#include <iostream>
#include <cstring>
#include <cmath>
#define N 100
using namespace std;

bool map[N][N],v[N];
int n,m,s,vel,link[N];
double gx[N],gy[N],hx[N],hy[N];

double dis(int x1,int y1,int x2,int y2){return sqrt(double((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));}

void input()
{
	int i,j;
	memset(link,-1,sizeof(link));
	memset(map,false,sizeof(map));
	for(i=0;i<n;i++)
		scanf("%lf%lf",&gx[i],&gy[i]);
	for(i=0;i<m;i++)
		scanf("%lf%lf",&hx[i],&hy[i]);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			if(dis(gx[i],gy[i],hx[j],hy[j])<=s*vel)
				map[i][j]=true;
}

bool dfs(int start)
{
	int i;
	for(i=0;i<m;i++)
	{
		if(!v[i]&&map[start][i])
		{
			v[i]=true;
			if(link[i]==-1 || dfs(link[i]))
			{
				link[i]=start;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int i,cnt;
	//freopen("in.txt","r",stdin);
	while(scanf("%d%d%d%d",&n,&m,&s,&vel)!=EOF)
	{
		input();
		for(i=cnt=0;i<n;i++,memset(v,false,sizeof(v)))
			if(dfs(i))
				cnt++;
		printf("%d\n",n-cnt);
	}
	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