KM最大权二分图匹配。然后权值的话，左侧原来的 m 个点代表送货员的家，与右侧表示红酒地点的 n 个点之间连边，权值为送货员的家 ni 与红酒处 mi 之间的距离与 mi 到 饭店之间距离的和，选中这条边的话表示这个人直接从家里到红酒处然后把酒送到了饭店。之后在左侧新建 n-1 个点表示走到店里又出来的送货员，其与右侧n个点的权值设为2倍红酒到饭店的距离，因为回到店里之后所有的送货员就没差别了，而且一个人可以被重复利用，没有什么先后的时间限制。n-1 是因为最多就只有 n-1 瓶红酒会被从店里又出来的人送到（至少有 1 个人是直接从家里到红酒处的）。这样直接跑KM就可以了，但是有个问题是原来的KM板子太慢了，到UOJ#80找了个新的板子，能1s跑2000个点的KM。。。
继续阅读“[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu”
http://codeforces.com/contest/1013/problem/D
题意：每次可以从矩形的3个角产生第4个角，问至少需要添加多少个方块可以使得让整张图都充满方块。
自己想的是奇怪的思路，因为发现一个联通的块可以扩展到这个块的maxx，maxy，但是之后就不知道怎么做了。看了题解才恍然大悟，原来是把坐标转化成二分图的左右节点，然后考虑连通分量的个数就可以了。证明的时候，首先注意到一点就是二分图中两个点之间的路径个数一定是奇数，对于同一个连通分量中的左右两个点x，y，他们之间的距离如果是1的话那说明二者之间一定有了一条路径了，也就是这个点已经有一个方块了，如果不是1那么至少是3，每次取距离y最近的3个点，按照题目中给的性质，就可以生成一条新的边，也就是从倒数第四个直接联到y，这样的话，每次边的数量都会-2，到最后一定能减少到1，回到之前的情况。所以在同一个连通分量里的左右所有的点一定能连到一起，也就是说所有的方块一定能被涂上。这时候等于说连通分量和能全部染色等价了，我们就只需要计算出来最少需要多少条边使整个图成为连通图就行了。。其实也就是 连通分量数-1
wa点的话因为把n+m写成了2*n错了还以为横纵坐标是一样大的。。。愚蠢的错误emmmm
比赛时候其实想的就是正解，但是没时间实现了。
这里并不是把猫狗分离开来，而是把voter分离开，换句话说原来的边变成了点，支持猫的在一边，支持狗的在另一边，如果有冲突的话连一条边，这样的话就是求最大独立集了。
本来看这个输入感觉头疼，后来想了想，忽然意识到：1 重复的人可以不用管，照例读入建立点，因为把他变成点之后对图没有任何影响。2 可以不用管字符后的数字，直接把他们当成一个整体就好了，整个字符串比较。 3 建立图的时候可以不用分左右两边，只要i和j有冲突就line[i][j]=line[j][i]=1；这样会使得建图的过程更简单，然后相当于把二分图对称了一下，最后输出的时候最大匹配数除以2就可以了.
