记录编号	396940	评测结果	AAAAAAAA
题目名称	[JSOI 2009] 星际争霸	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-04-19 15:21:05	内存使用	0.31 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 60;
const int INF = 0x7fffffff;

inline int in(void){
	char tmp = getchar();
	int res = 0, f = 1;
	while(!isdigit(tmp) && tmp != '-')tmp = getchar();
	if(tmp == '-')f = -1, tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res * f;
}

struct DATA{
	int x, y, z;
	
	DATA(){;}
	DATA(int a, int b, int c){
		x = a, y = b, z = c;
	}
	
	int len(void){
		return x * x + y * y + z * z;
	}
};

struct EDGE{
	int fr, to, ne;
	int cap;
	
	EDGE(){;}
	EDGE(int a, int b, int c, int d){
		fr = a, to = b, ne = c;
		cap = d;
	}
};

inline void add_edge(int fr, int to, int cap);
bool BFS(void);
inline int get_flow(void);

vector<EDGE> edge;
vector<DATA> data;
int head[MAXN];
int S, T, max_flow;
int pre[MAXN];
int N, M, R;

int main(){
#ifndef LOCAL
	freopen("starwar.in", "r", stdin);
	freopen("starwar.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	memset(head, 0xff, sizeof(head));
	
	N = in(), M = in(), R = in();
	R = R * R, S = 0, T = N + 1;
	
	data.push_back(DATA(0, 0, 0));
	for(int i = 1, a, b, c; i <= N; ++i){
		a = in(), b = in(), c = in();
		data.push_back(DATA(a, b, c));
	}
	
	for(int i = 1, a, b, k1, k2, k3, len; i <= M; ++i){
		a = in(), b = in();
		k1 = data[a].x - data[b].x;
		k2 = data[a].y - data[b].y;
		k3 = data[a].z - data[b].z;
		len = k1 * k1 + k2 * k2 + k3 * k3;
		add_edge(a, b, len);
		add_edge(b, a, len);
	}
	
	bool flag = false;
	for(int i = 1; i <= N; ++i){
		if(data[i].len() >= R){
			add_edge(i, T, INF);
			flag = true;
		}
	}
	if(!flag){
		printf("0\n");
		return 0;
	}
	
	while(BFS()){
		max_flow += get_flow();
	}
	
	printf("%d\n", max_flow);
	return 0;
}

inline void add_edge(int fr, int to, int cap){
	edge.push_back(EDGE(fr, to, head[fr], cap)), head[fr] = edge.size() - 1;
	edge.push_back(EDGE(to, fr, head[to], 0)), head[to] = edge.size() - 1;
	return ;
}

bool BFS(void){
	static bool vis[MAXN];
	static queue<int> que;
	static int now, to;
	
	memset(vis, 0x00, sizeof(vis));
	memset(pre, 0xff, sizeof(pre));
	while(!que.empty())que.pop();
	
	que.push(S);
	vis[S] = true;
	
	while(!que.empty()){
		now = que.front();
		que.pop();
		if(now == T)return true;
		for(int i = head[now]; ~i; i = edge[i].ne){
			if(!edge[i].cap || vis[to = edge[i].to])continue;
			que.push(to);
			vis[to] = true;
			pre[to] = i;
		}
	}
	return false;
}

inline int get_flow(void){
	int now = pre[T], min_flow = INF;
	
	while(~now){
		min_flow = min(min_flow, edge[now].cap);
		now = pre[edge[now].fr];
	}
	
	now = pre[T];
	while(~now){
		edge[now].cap -= min_flow;
		edge[now ^ 1].cap += min_flow;
		now = pre[edge[now].fr];
	}
	
	return min_flow;
}