记录编号	155721	评测结果	AAAAAAAA
题目名称	[JSOI 2009] 星际争霸	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-03-30 00:02:40	内存使用	0.38 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define getc() getchar() 
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 53, maxm = 5603, INF = 0x3f3f3f3f;
struct Edge{int to, cast;Edge *rev;void init(int a, int c, Edge *r){to = a,cast = c, rev = r;}}E[maxm], *Eend = E;
#include <queue>
Edge *adj[maxn][maxn];
int N, T, adj_size[maxn], dis[maxn], NowE[maxn];
bool vis[maxn];

inline void AddE(int u, int v, int c){
	Eend->init(v, c, Eend+1);adj[u][adj_size[u]++] = Eend++;
	Eend->init(u, 0, Eend-1);adj[v][adj_size[v]++] = Eend++;
}

inline void init(){
	int i, j, x[maxn], y[maxn], z[maxn], m, d, a, b, c, R;
	getd(N); getd(m); getd(R); T = N + 1;
	*x = *y = *z = 0;
	for(i = 1;i <= N;++i)getd(x[i]), getd(y[i]), getd(z[i]);
	while(m--){
		getd(i), getd(j);
		a = x[j] - x[i], b = y[j] - y[i], c = z[j] - z[i];
		d = a * a + b * b + c * c;
		if(j)AddE(i, j, d);
		if(i)AddE(j, i, d);
	}
	bool ok = 0;
	for(i = 1;i <= N;++i)if(x[i] * x[i] + y[i] * y[i] + z[i] * z[i] > R * R)
		AddE(i, T, INF), ok = 1;
	if(!ok){
		printf("0\n");
		exit(0);
	}
}

inline bool BFS(){
	memset(vis, 0, sizeof(vis));
	static queue<int> Q;Q.push(0);vis[0] = true;
	int cur, i;
	Edge *e;
	while(!Q.empty()){
		cur = Q.front();Q.pop();
		for(i = 0;i < adj_size[cur];++i)if((e = adj[cur][i])->cast && !vis[e->to]){
			dis[e->to] = dis[cur] + 1;
			vis[e->to] = true;
			Q.push(e->to);
		}
	}
	return vis[T];
}

int DFS(int cur, int res){
	if(cur == T || !res)return res;
	int i, ans = 0, t;
	Edge *e;
	for(i = NowE[cur];i < adj_size[cur] && res;++i)if(dis[(e = adj[cur][i])->to] == dis[cur] + 1 && e->cast){
		t = DFS(e->to, min(res, e->cast));
		ans += t, res -= t;
		e->cast -= t, e->rev->cast += t;
	}
	return ans;
}

inline void work(){
	int ans = 0;
	while(BFS()){
		memset(NowE, 0, sizeof(NowE));
		ans += DFS(0, INF);
	}
	printf("%d\n", ans);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(starwar);
#endif
	init();
	work();

#ifdef DEBUG
	printf("\n%lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}