记录编号	16183	评测结果	AAAAAAAA
题目名称	[JSOI 2009] 星际争霸	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2010-04-21 17:38:40	内存使用	0.33 MiB

#include<fstream.h>
#include<cmath>
#include<cstring>
using namespace std;
ifstream fin("starwar.in");
ofstream fout("starwar.out");

int main()
{
	static int flow[100][100],limit[100][100];
	static bool check[100];
	static int last[100];
	int n,m,r,i,j,ans,delta,r1,r2,x1,max=1000000000;
	int x[100],y[100],z[100];
	ans=0;
	fin>>n>>m>>r;
	r=r*r;
	for (i=1;i<=n;i++)
	{
		fin>>x[i]>>y[i]>>z[i];
	}
	x[0]=0;
	y[0]=0;
	z[0]=0;
	for (i=1;i<=m;i++)
	{
		fin>>r1>>r2;
		limit[r1+1][r2+1]=(x[r1]-x[r2])*(x[r1]-x[r2])+(y[r1]-y[r2])*(y[r1]-y[r2])+(z[r1]-z[r2])*(z[r1]-z[r2]);
		limit[r2+1][r1+1]=limit[r1+1][r2+1];
	}
	for (i=2;i<=n+1;i++)
		if (x[i-1]*x[i-1]+y[i-1]*y[i-1]+z[i-1]*z[i-1]>r)
			limit[i][n+2]=max;
	for (;;)
	{
		for (i=1;i<=n+2;i++)
		{
			last[i]=0;
			check[i]=false;
		}
		last[1]=10000;
		do
		{
			i=0;
			do
			{
				i++;
			}while ((i<=n+2) && ((last[i]==0) || (check[i])));
			if (i>n+2)
				break;
			for (j=1;j<=n+2;j++)
				if (last[j]==0)
				{
					if (flow[i][j]<limit[i][j])
						last[j]=i;
					else
						if (flow[j][i]>0)
							last[j]=0-i;
				}
			check[i]=true;
		}while (last[n+2]==0);
		if (last[n+2]==0)
			break;
		delta=max;
		i=n+2;
		do
		{
			j=i;
			i=abs(last[j]);
			if (last[j]>0)
				x1=limit[i][j]-flow[i][j];
			else
				x1=flow[j][i];
			if (x1<delta)
				delta=x1;
		}while (i!=1);
		i=n+2;
		do
		{
			j=i;
			i=abs(last[j]);
			if (last[j]>0)
				flow[i][j]+=delta;
			else
				flow[j][i]-=delta;
		}while (i!=1);
		ans+=delta;
	}
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}