记录编号	16146	评测结果	AAAAAAAA
题目名称	[JSOI 2009] 星际争霸	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2010-04-21 12:09:23	内存使用	0.47 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;
const int maxn=1000;
const int maxm=20000;
const int oo=2000000000;


struct 
{
	int x,y,z;
	bool safe;
}p[52];

int f[52][52];
int d[maxn],vd[maxn],ans;

struct edge
{
	int t,c,v;
	edge *next,*op;
}E[10000],*V[52];
int eh;
inline void addedge(int a,int b,int c)
{
	E[++eh].next=V[a];  V[a]=E+eh; V[a]->c = c; V[a]->t=b;
	E[++eh].next=V[b];  V[b]=E+eh; V[b]->c = 0; V[b]->t=a;
	V[a]->op=V[b];  V[b]->op=V[a];
}

int n,m,r,S,T,maxmax;

void init()
{
	scanf("%d%d%d",&n,&m,&r);
	S=0;T=n+1;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
		if (p[i].x*p[i].x+p[i].y*p[i].y+p[i].z*p[i].z>r*r) 
		{	
			p[i].safe=true;
			addedge(i,T,oo);
		}
	}
	int a,b;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		f[a][b]=(p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y)+(p[a].z-p[b].z)*(p[a].z-p[b].z);
		maxmax+=f[a][b];
		addedge(a,b,f[a][b]);
		addedge(b,a,f[a][b]);
	}
}

int dfs(int u,int flow)
{
	int now=0;
	if (u==T) return flow;
	for (edge *e=V[u];e;e = e->next)
	{
		int v=e->t;
		if (e->c > 0 && d[u]==d[v]+1)
		{
			int t=dfs(v,min(flow-now,e->c));
			if (t)
			{
				e->c -= t;
				e->op->c += t;
				now += t;
				if (now==flow) return now;
			}
		}
	}
	if (d[S]>=n) return now;
	if (--vd[d[u]]==0) d[S]=n;
	vd[++d[u]]++;
	return now;
}

void SAPflow()
{
	n=n+2;
	vd[0]=n;
	while (d[S]<n)
	ans+=dfs(S,oo);
}

int main()
{
	freopen("starwar.in","r",stdin);
	freopen("starwar.out","w",stdout);
	init();
	SAPflow();
	printf("%d\n",ans);
}