记录编号	98290	评测结果	AAAAAAAAAA
题目名称	[CTSC 2000] 丘比特的烦恼	最终得分	100
用户昵称	FF_Sky||幻	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2014-04-22 16:11:50	内存使用	0.42 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#define NN 70
#define MM 2000
using namespace std;

int ver[MM],next[MM],d[NN],head[NN],tot = 1,n,st,ed,nn,q[MM],ans,c[MM],ff[MM],front[NN],w[NN][NN];
int x[NN],y[NN],k,kk[NN][NN],ss[NN][NN];
string s[NN];
bool v[NN],vv[NN][NN];

void add(int x,int y){
	c[++tot] = 1; ver[tot] = y; ff[tot] = x; next[tot] = head[x]; head[x] = tot;
	c[++tot] = 0; ver[tot] = x; ff[tot] = y; next[tot] = head[y]; head[y] = tot;
}

bool bfs(){
	int l,r,x,j;
	memset(d,128,sizeof(d));
	memset(v,0,sizeof(v));
	l = 1; r = 1;
	q[l] = st;
	d[st] = 0;
	while (l <= r){
		x = q[l];
		l++;
		v[x] = 0;
		for (j = head[x]; j; j = next[j]){
			if (d[ver[j]] < d[x]+w[x][ver[j]] && c[j] > 0){
				d[ver[j]] = d[x]+w[x][ver[j]];
				front[ver[j]] = j;
				if (!v[ver[j]]){
					v[ver[j]] = 1;
					q[++r] = ver[j];
				}
			}
		}
	}
	if (d[ed] != d[ed+1]) return 1;
	return 0;
}

bool judge(int x,int y,int xx,int yy,int xxx,int yyy){
	if (xxx>=min(x,xx) && xxx<=max(x,xx) && yyy>=min(y,yy) && yyy<=max(y,yy) && (xx-x)*(yyy-y)-(xxx-x)*(yy-y)==0) return 1;
	return 0;
}

void upcase(string &s){
	int len = s.length();
	for (int i = 0; i < len; i++){
		if (s[i] >= 'a' && s[i] <= 'z') s[i] -= 32;
	}
}

void update(){
	int i;
	for (i = front[ed]; i; i = front[ff[i]]){
		c[i]--;
		c[i^1]++;
	}
	ans += d[ed];
}

int main(){
	freopen("cupid.in","r",stdin);
	freopen("cupid.out","w",stdout);
	int i,t1,t2,temp,j,ii;
	bool flag;
	string s1,s2;
	scanf("%d",&k);
	k = k*k;
	scanf("%d",&n);
	nn = n<<1;
	st = 0; ed = nn+1;
	for (i = 1; i <= nn; i++){
		cin >> x[i] >> y[i] >> s[i];
		upcase(s[i]);
	}
	for (i = 1; i <= n; i++)
		for (j = n+1; j <= nn; j++){
			ss[i][j] = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
		}
	for (i = 1; i <= n; i++){
		add(st,i);
		add(i+n,ed);
	}
	cin >> s1;
	while (s1 != "End"){
		cin >> s2 >> temp;
		upcase(s1);
		upcase(s2);
		for (i = 1; i <= nn; i++){
			if (s[i] == s1){
				t1 = i;
				break;
			}
		}
		for (i = 1; i <= nn; i++){
			if (s[i] == s2){
				t2 = i;
				break;
			}
		}
		if (t1 > t2) swap(t1,t2);
		if (ss[t1][t2] <= k){
			if (!vv[t1][t2]){
				flag = 0; vv[t1][t2] = 1;
				for (i = 1; i <= nn; i++){
					if (i != t1 && i != t2 && judge(x[t1],y[t1],x[t2],y[t2],x[i],y[i])){
						flag = 1;
						break;
					}
				}
				if (!flag){
					add(t1,t2);
					w[t1][t2] = temp;
					w[t2][t1] = -temp;
				}
			}
			else
				if (w[t1][t2] > 0) w[t1][t2] = temp,w[t2][t1] = -temp;
		}
		cin >> s1;
	}
	for (i = 1; i <= n; i++)
		for (j = n+1; j <= nn; j++){
			if (!vv[i][j] && ss[i][j] <= k){
				flag = 0;
				for (ii = 1; ii <= nn; ii++){
					if (ii != i && ii != j && judge(x[i],y[i],x[j],y[j],x[ii],y[ii])){
						flag = 1;
						break;
					}
				}
				if (!flag) add(i,j),w[i][j] = 1,w[j][i] = -1;
			}
		}
	while (bfs())
		update();
	printf("%d\n",ans);
	return 0;
}