题目大意
给定一张无向带权平面图每个点的坐标以及每条边的边权，求这张图最大割的大小。一个割定义为将图的点集分成不交的两个部分的方案，割的大小为所有两端点不在同一部分中的边的边权和。
数据范围
点数 $n$ 满足 $1\leq n\leq 200$，边数 $m$ 满足 $1\leq m\leq 1000$。边权为 $[0,10^5]$ 中的整数，坐标的绝对值不超过 $10^4$。
解题过程
对于图的某个割，若某条边的两个端点在同一部分中，则将这条边删去，将两个端点合并为一个点。重复执行直到所有边的两个端点都不在同一部分，由定义可知得到的新图是一张二分图。
求出原平面图的每个面，其在新图中，要么对应一个面，要么面上所有点被缩在一起。新图是二分图意味着，原平面图的每个面，恰有偶数条边没有被删去，即恰有偶数条边满足两端点不在同一部分。
另一方面，对于任意一个原图的边集，满足每个面恰有偶数条边被包含在边集中，都存在一个割满足该边集恰好是所有两端点不在同一部分的边的集合。这是因为，当且仅当一张平面图的所有面都包含偶数条边时，该平面图是二分图，于是我们进行上述缩点后二分图染色，即可得到一种合法的方案。
对于平面图，其中的每条边被所有面恰好包含两次，我们建出原图的对偶图，则对偶图的每个顶点对应了原图的一个面，对偶图的每条边对应了原图的一条边，连接了原图中包含它的两个面。特别地，若在原图中某条边被同一个面包含了两次，则它对应对偶图中的一个自环。
经过上面的转化，问题变为：给定一张无向带权图，求出它的某个生成子图，使得每个点的度数均为偶数，且生成子图的边权和尽量大。考虑某个合法生成子图的补图，我们令奇度数点的集合为 $S$，给出如下引理：
引理：一个合法生成子图的补图一定可以拆分为 $\frac{1}{2}|S|$ 条边不重复的路径和若干个环，且 $S$ 中每个点恰好作为某条路径的端点出现一次。
证明：关于 $|S|$ 归纳。$S$ 为空时显然补图的每个点度数为偶数，即补图由若干个环组成。$S$ 不为空时，由每个连通块恰有偶数个奇度数点知存在两个点 $u,v\in S$ 联通。找到一条 $u$ 到 $v$ 的路径从补图中删去，结合归纳条件可知引理成立。
我们求出图上所有奇度数点两两间最短路。并求出以最短路为权值的完全图的最小权完美匹配，由引理知一个合法生成子图的补图权值和一定大于这个完美匹配的边权和，与此同时我们选择所有在偶数（包括 $0$）条路径中出现的边可以得到一个合法的生成子图，所以这个完美匹配的边权和即为所求答案，使用前文所述方法可以构造一个合法方案。这个做法的时间复杂度是 $O(n^3)$。