3080626_ac_7421ms_508k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define MaxV 210

int n, M;
int ans, sum;
struct node
{
	int map[MaxV][MaxV];
}t2, t1;

double pos[110][2];
double D;

int reachable(int i, int j)
{
	return (pos[i][0]-pos[j][0])*(pos[i][0]-pos[j][0])+(pos[i][1]-pos[j][1])*(pos[i][1]-pos[j][1]) <= D;
}

void input()
{
	int i, j;
	int m, c;

	scanf("%d%lf",&n,&D);
	D *= D;
	sum = 0;
	memset(t1.map,0,sizeof(t1.map));
	for(i = 1; i <= n; i++)
	{
		scanf("%lf%lf%d%d",&pos[i][0],&pos[i][1],&c,&m);
		sum += c;
		if(c!=0)
		{
			t1.map[0][i] += c;
		}
		t1.map[i][i+n] += m;
	}
	for(i = 1; i <= n; i++)
	{
		for(j = i+1; j <= n; j++)
		{
			if(reachable(i,j))
			{
				t1.map[i+n][j] += 1000;
				t1.map[j+n][i] += 1000;
			}
		}
	}
}

int bfs(int m)
{
	int i, mark = 0;
	int f, r, p;
	int pre[MaxV], visited[MaxV];
	int queue[MaxV];
	int C, F[MaxV];

	f = r = -1;
	memset(pre,0,sizeof(pre));
	memset(visited,0,sizeof(visited));
	visited[0] = 1;queue[++f] = 0;pre[0] = -1;
	C = 2100000000;
	while(f!=r)
	{
		++r;
		p = queue[r];
		for(i = 0; i < M; i++)
			if(t2.map[p][i]&&!visited[i])
			{
				visited[i] = 1;
				queue[++f] = i;
				pre[i] = p;
				F[i] = t2.map[p][i];
				if(i==m-1)
				{	
					mark = 1;
					goto m1;
				}
			}
	}
	m1:;
	if(mark)
	{
		p = m-1;
		while(pre[p]!=-1)
		{
			if(F[p]<C)
				C = F[p];
			p = pre[p];
		}
		p = m-1;
		while(pre[p]!=-1)
		{
			t2.map[pre[p]][p] -= C;
			t2.map[p][pre[p]] += C;
			p = pre[p];
		}
		ans += C;
	}
	return mark;
}

int main()
{
	int i, cas, flag;

	scanf("%d",&cas);
	while(cas--)
	{
		input();
		M = 2*n+1;flag = 1;
		for(i = 1; i <= n; i++)
		{
			t2 = t1;
			ans = 0;
			while(bfs(i+1));
			if(sum==ans)
			{
				flag = 0;
				printf("%d ",i-1);
			}
		}
		if(flag)
			printf("-1");
		puts("");
	}
	return 0;
}