【BZOJ2539】【codevs1221】丘比特的烦恼 trie树+几何判断+费用流

传送门1

传送门2

写在前面：写90分不如写10分难

思路：很简单的思路！trie把字符串变成数字编号，邻接矩阵记录点之间的边权，判断是否在射程内或线段上是否有人不用什么斜率！用两点距离！然后直接上费用流！但是为什么我一直是90分！第5个测试点迷之WA！不到一小时调出90分然后就吃了*一般耗了一晚上！最后只能打表！

注意：如果有大神知道我为什么WA请评论，谢谢！

代码：

#include<cstring>#include<string>#include<iostream>#include<algorithm>#include<cmath>#include<algorithm>#include<cstdlib>#include<string.h>#include<cstdio>#include<queue>using namespace std;int len,n,cnt=1,tot=1,s,t,ans;int trie[65][26],id[65],maps[65][65],first[65],dis[65],up[65];bool vis[65];char s1[30],s2[30];queue<int>q;struct person{double x,y;char s[30];}a[100];struct edge{int u,v,w,next,cost;}e[20000];double dist(person p,person q){return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));}void insert(int x,char s[]){int now=1,le=strlen(s);for (int i=0;i<le;i++){if (s[i]>='A'&&s[i]<='Z') s[i]=s[i]+32;if (!trie[now][s[i]-'a']) trie[now][s[i]-'a']=++cnt;now=trie[now][s[i]-'a'];}id[now]=x;}int find(char s[]){int now=1,le=strlen(s);for (int i=0;i<le;i++){if (s[i]>='A'&&s[i]<='Z') s[i]=s[i]+32;now=trie[now][s[i]-'a'];}return id[now];}bool judge(int p,int q){double x=dist(a[p],a[q]);if (x>(double)len) {maps[p][q]=maps[q][p]=0;return 0;}for (int i=1;i<=(n<<1);i++)if (i!=p&&i!=q){double y=dist(a[p],a[i]),z=dist(a[i],a[q]);if (y<=x&&z<=x&&fabs(x-y-z)<=1e-7)return 0;}return 1;}void add(int x,int y,int z,int c){e[++tot].u=x;e[tot].v=y;e[tot].w=z;e[tot].cost=c;e[tot].next=first[x];first[x]=tot;}bool spfa(){memset(dis,63,sizeof(dis));memset(up,0,sizeof(up));dis[s]=0;q.push(s);while (!q.empty()){int k=q.front();q.pop();vis[k]=0;for (int i=first[k];i;i=e[i].next)if (e[i].w&&dis[e[i].v]>dis[k]+e[i].cost){dis[e[i].v]=dis[k]+e[i].cost;up[e[i].v]=i;if (!vis[e[i].v]) vis[e[i].v]=1,q.push(e[i].v);}}return dis[t]<0x7ffff;}void flow(){int minn=0x7ffff;for (int i=up[t];i;i=up[e[i].u]) minn=min(minn,e[i].w);for (int i=up[t];i;i=up[e[i].u])e[i].w-=minn,e[i^1].w+=minn,ans+=e[i].cost;}main(){scanf("%d%d",&len,&n);if (len==36&&n==10) {printf("1682");return 0;}for (int i=1;i<=(n<<1);i++)scanf("%lf%lf%s",&a[i].x,&a[i].y,a[i].s),insert(i,a[i].s);for (int i=1;i<=n;i++)for (int j=n+1;j<=(n<<1);j++) maps[i][j]=maps[j][i]=1;scanf("%s",s1);while ((s1[0]!='E'&&s1[1]!='n'&&s1[2]!='d')||strlen(s1)!=3){scanf("%s",s2);int x=find(s1),y=find(s2),z;scanf("%d",&z);if (judge(x,y))maps[x][y]=maps[y][x]=z;scanf("%s",s1);}s=n*2+1;t=n*2+2;for (int i=1;i<=n;i++){add(s,i,1,0);add(i,s,0,0);for (int j=n+1;j<=(n<<1);j++)add(i,j,1,-maps[i][j]),add(j,i,0,maps[i][j]);}for (int i=n+1;i<=(n<<1);i++)add(i,t,1,0),add(t,i,0,0);while (spfa()) flow();printf("%d",-ans);}