丘比特的烦恼
题目描述 Description
随着社会的不断发展，人与人之间的感情越来越功利化。最近，爱神丘比特发现，爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼，他越来越难找到合适的男女，并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国，找到了掌管东方人爱情的神——月下老人，向他求教。
月下老人告诉丘比特，纯洁的爱情并不是不存在，而是他没有找到。在东方，人们讲究的是缘分。月下老人只要做一男一女两个泥人，在他们之间连上一条红线，那么它们所代表的人就会相爱——无论他们身处何地。而丘比特的爱情之箭只能射中两个距离相当近的人，选择的范围自然就小了很多，不能找到真正的有缘人。
丘比特听了月下老人的解释，茅塞顿开，回去之后用了人间的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。这样，射中有缘人的机会也增加了不少。
情人节(Valentine's day)的午夜零时，丘比特开始了自己的工作。他选择了一组数目相等的男女，感应到他们互相之间的缘分大小，并依此射出了神箭，使他们产生爱意。他希望能选择最好的方法，使被他选择的每一个人被射中一次，且每一对被射中的人之间的缘分的和最大。
当然，无论丘比特怎么改造自己的弓箭，总还是存在缺陷的。首先，弓箭的射程尽管增大了，但毕竟还是有限的，不能像月下老人那样，做到“千里姻缘一线牵”。其次，无论怎么改造，箭的轨迹终归只能是一条直线，也就是说，如果两个人之间的连线段上有别人，那么莫不可向他们射出丘比特之箭，否则，按月下老人的话，就是“乱点鸳鸯谱”了。
作为一个凡人，你的任务是运用先进的计算机为丘比特找到最佳的方案。
输入描述
Input Description
输入文件第一行为正整数k，表示丘比特之箭的射程，第二行为正整数n(n<30)，随后有2n行，表示丘比特选中的人的信息，其中前n行为男子，后n行为女子。每个人的信息由两部分组成：他的姓名和他的位置。姓名是长度小于20且仅包含字母的字符串，忽略大小写的区别，位置是由一对整数表示的坐标，它们之间用空格分隔。格式为x y Name。输入文件剩下的部分描述了这些人的缘分。每一行的格式为Name1 Name2 p。Name1和Name2为有缘人的姓名，p是他们之间的缘分值(p为小于等于255的正整数)。以一个End作为文件结束标志。每两个人之间的缘分至多只被描述一次。如果没有被描述，则说明他们缘分值为1。
输出描述
Output Description
输出文件仅一个正整数，表示每一对被射中的人之间的缘分的总和。这个和应当是最大的。
样例输入
Sample Input
2
3
0 0 Adam
1 1 Jack
0 2 George
1 0 Victoria
0 1 Susan
1 2 Cathy
Adam Cathy 100
Susan George 20
George Cathy 40
Jack Susan 5
Cathy Jack 30
Victoria Jack 20
Adam Victoria 15
End
样例输出
Sample Output
65
数据范围及提示
Data Size & Hint
n<30
p为小于等于255的正整数
思路：
就是建图跑二分图最优匹配，这里我用最小费用流求解。
几个需要注意的地方：
- 点以坐标形式给出，要运用一下计算机和的知识求出两点间距离、判断两点所连线段上是否有其他点；
- 点的特征值是一个字符串，且不区分大小写，需要注意；
- 题面保证没有重边但数据中有重边，且是取最后给出的边，这里比较坑。一是保证没有重边却出现重边debug了很久；二是想到可能存在重边但没想到竟不是取最好的边debug了更久（不过使用领接矩阵的话恰好跳过了这个坑点，大概标程写的KM吧）；
- 数据中未给出的边存在默认权值为一的边，优先级低于距离限制和夹点限制。
代码：
#include<iostream>
#include<queue>
#include<cstdio>
#include<vector>
#include<map>
#include<cmath>
#include<cstring> using namespace std;
const int maxn = 2e4+5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-4; struct Edge
{
int from, to, cap, flow, cost;
}; struct MCMF
{
int n, m, s, t;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];//是否在队列
int d[maxn];//Bellman-Ford用
int p[maxn];//上一条弧
int a[maxn];//可改进量 void init(int n)
{
this->n=n;
for(int i=0; i<n; ++i)
G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap, int cost)
{
edges.push_back((Edge)
{
from, to, cap, 0, cost
});
edges.push_back((Edge)
{
to, from, 0, 0, -cost
});
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
} bool BellmanFord(int s, int t, int &flow, int& cost)
{
for(int i=0; i<n; ++i)
d[i]=INF;
memset(inq,0,sizeof(inq));
memset(p,0,sizeof(p));
d[s]=0;
inq[s]=1;
p[s]=0;
a[s]=INF; queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
inq[u]=0;
for(int i=0; i<G[u].size(); ++i)
{
Edge& e=edges[G[u][i]];
if(e.cap > e.flow && d[e.to] > d[u] + e.cost)
{
d[e.to]=d[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=min(a[u],e.cap-e.flow);
if(!inq[e.to])
{
Q.push(e.to);
inq[e.to]=1;
}
}
}
}
if(d[t]==INF)
return false;
flow+=a[t];
cost+=d[t]*a[t];
int u=t;
while(u!=s)
{
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
u=edges[p[u]].from;
}
return true;
} int MinCost(int s, int t)
{
int flow=0, cost=0;
while(BellmanFord(s,t,flow,cost))
{
}
return cost;
}
} mcmf; class Person
{
public:
int x, y, num;
string name; Person() {} Person(int a, int b, int c, string str):x(a), y(b), num(c), name(str)
{
}
}; int k, n, s, t;
int grap[100][100];
map<string, int> msi;
vector<Person> persons; double Slope(Person& p1, Person& p2)
{
if(p1.x==p2.x)
return INF;
return 1.0*(p1.y-p2.y)/(p1.x-p2.x);
} int GetDis(Person& p1, Person& p2)
{
int maxx=p1.x, maxy=p1.y, minx=p2.x, miny=p2.y;
double sp=Slope(p1, p2);
if(maxx<minx) swap(maxx, minx);
if(maxy<miny) swap(maxy, miny);
for(int i=0; i<persons.size(); ++i)
{
if(i==p1.num || i==p2.num) continue;
Person& p3=persons[i];
if(p3.x<=maxx && p3.x>=minx && p3.y<=maxy && p3.y>=miny && abs(sp-Slope(p1, p3))<=eps)
return INF;
}
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
} void trans(string& str)
{
for(int i=0; i<str.size(); ++i)
if(str[i]>='A' && str[i]<='Z')
str[i]+=32;
} void Init()
{
msi.clear();
persons.clear();
for(int i=0; i<100; ++i)
for(int j=0; j<100; ++j)
grap[i][j]=1;
cin>>k>>n;
k*=k;
int x, y, fate, dis;
string name, name2;
s=2*n;
t=s+1;
mcmf.init(t+1);
for(int i=0; i<2*n; ++i)
{
cin>>x>>y>>name;
trans(name);
persons.push_back(Person(x, y, i, name));
if(i<n)
mcmf.AddEdge(s, i, 1, 0);
else
mcmf.AddEdge(i, t, 1, 0);
msi[name]=i;
}
while(cin>>name)
{
if(name=="End")
break;
trans(name);
cin>>name2>>fate;
trans(name2);
int p1=msi[name], p2=msi[name2];
if(p1>p2) swap(p1, p2);
grap[p1][p2]=fate;
}
for(int i=0; i<n; ++i)
for(int j=n; j<2*n; ++j)
{
dis=GetDis(persons[i], persons[j]);
if(dis<=k)
mcmf.AddEdge(i, j, 1, -grap[i][j]);
}
} int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Init();
cout<<-mcmf.MinCost(s, t)<<endl;
return 0;
}