记录编号	9407	评测结果	AAAAAAAAAA
题目名称	[CTSC 2000] 丘比特的烦恼	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2009-03-25 13:35:29	内存使用	0.28 MiB

/* 
 * Problem: 丘比特的烦恼
 * Author: Guo Jiabao
 * Time: 2009.3.25 13:34
 * State: Solved
 * Memo: SPFA flow
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=61,MAXL=21,INF=0x7FFFFFFF;
using namespace std;
struct Queue
{
	int Q[MAXN],Head,Tail,size;
	bool inq[MAXN];
	Queue()
	{
		memset(inq,0,sizeof(inq));
		Head=0;Tail=-1;size=0;
	}
	void ins(int p)
	{
		inq[p]=true;
		size++;
		if (++Tail>=MAXN) Tail=0;
		Q[Tail]=p;
	}
	int pop()
	{
		int r=Q[Head];
		size--;
		if (++Head>=MAXN) Head=0;
		inq[r]=false;
		return r;
	}
}Q;
struct Person
{
	char Name[MAXL];
	int x,y;
}P[MAXN];
struct edge
{
	edge *next,*op;
	int t,v,c;
};
int N,M,T,Distance,S,Tar,Ans;
int adj[MAXN][MAXN],sp[MAXN],ft[MAXN];
edge *V[MAXN],*pt[MAXN];
inline int dist2(int x1,int y1,int x2,int y2)
{
	return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
inline bool iscross(int a,int b,int c)
{
	if ((P[a].x-P[b].x)*(P[b].y-P[c].y) == (P[b].x-P[c].x)*(P[a].y-P[b].y)) //共线
	{
		if (P[a].y==P[c].y)
			return (P[a].x < P[b].x && P[b].x < P[c].x)||(P[c].x < P[b].x && P[b].x < P[a].x);
		else
			return (P[a].y < P[b].y && P[b].y < P[c].y)||(P[c].y < P[b].y && P[b].y < P[a].y);
	}
	return false;
}
void shot()
{
	int i,j,k;
	for (i=1;i<=N;i++)
		for (j=M;j<=T;j++)
		{
			if (dist2(P[i].x,P[i].y,P[j].x,P[j].y)>Distance*Distance)
				adj[i][j]=0;
			else
			{
				for (k=1;k<=T;k++)
					if (k!=i && k!=j && iscross(i,k,j))
						break;
				adj[i][j]=k>T?1:0;
			}
		}
}
inline int scanname(char *S)
{
	for (int i=1;i<=T;i++)
		if (strcmp(P[i].Name,S)==0)
			return i;
}
void format(char *s)
{
	for (;*s;s++)
		if (*s>='a' && *s<='z')
			*s=*s-'a'+'A';
}
void addedge(int a,int b,int c=1,int v=0)
{
	edge e1={V[a],0,b,v,c},e2={V[b],0,a,-v,0};
	V[a]=new edge(e1);
	V[b]=new edge(e2);
	V[a]->op=V[b];V[b]->op=V[a];
}
void init()
{
	int i,j,a,b,c,v;char Name[MAXL];
	freopen("cupid.in","r",stdin);
	freopen("cupid.out","w",stdout);
	scanf("%d%d",&Distance,&N);
	M=N+1;T=N+N;
	for (i=1;i<=T;i++)
	{
		scanf("%d%d%s",&P[i].x,&P[i].y,P[i].Name);
		format(P[i].Name);
	}
	shot();
	while (scanf("%s",Name)!=EOF)
	{
		if (strcmp(Name,"End")==0) break;
		format(Name);
		a=scanname(Name);
		scanf("%s",Name);format(Name);
		b=scanname(Name);
		scanf("%d",&v);
		if (a>b) {c=a;a=b;b=c;}
		if (adj[a][b]!=0)
			adj[a][b]=v;
	}
	S=0;Tar=T+1;
	for (i=1;i<=N;i++)
		for (j=M;j<=T;j++)
			if (adj[i][j])
				addedge(i,j,1,adj[i][j]);
	for (i=1;i<=N;i++)
		addedge(S,i);
	for (i=M;i<=T;i++)
		addedge(i,Tar);
}
bool spfa()
{
	int i,j;
	for (i=S;i<=Tar;i++)
		sp[i]=-INF;
	sp[S]=0;
	Q.ins(S);
	while (Q.size)
	{
		i=Q.pop();
		for (edge *k=V[i];k;k=k->next)
		{
			j=k->t;
			if (k->c>0 && sp[i]+k->v>sp[j])
			{
				sp[j]=sp[i]+k->v;
				pt[j]=k;ft[j]=i;
				if (!Q.inq[j])
					Q.ins(j);
			}
		}
	}
	return sp[Tar]!=-INF;
}
void augment()
{
	int delta=INF,cf=0,i;
	for (i=Tar;i!=S;i=ft[i])
	{
		if (pt[i]->c<delta)
			delta=pt[i]->c;
	}
	for (i=Tar;i!=S;i=ft[i])
	{
		pt[i]->c-=delta;
		pt[i]->op->c+=delta;
		cf+=delta*pt[i]->v;
	}
	Ans+=cf;
}
void SpfaFlow()
{
	while (spfa())
		augment();
}
int main()
{
	init();
	SpfaFlow();
	printf("%d\n",Ans);
	return 0;
}