hdu 3722 Card Game (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 3722题目链接

题意:n个串,a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。

思路:先暴力处理出每两个的权值。。200*200*1000的复杂度。。还是可以接受的。。

然后把每个串看成了一个点,由于一个串最多可以被放在前面一次,被放在后面一次,所以可以类比图论中的环的入度和出度为1.

然后跑一遍KM. 1A,开心。

 

hdu 3435 A new Graph Game (有向环覆盖,拆点,二分图最优匹配,KM算法)

hdu 3435题目链接

题意:给你一张图,图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值

思路:题意杀啊。。。什么鬼了。。。然后时间。。1000的数据。。n3复杂度。。。还多组数据。。。。不是很懂这个时间是怎么算的。。为毛才2600MS啊。。。。

选区_073

 

做法同hdu 1853…

 

 

hdu 1853 Cyclic Tour (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 1853 题目链接

题意:一个带权有向图,要求找出若干的环,满足每个点恰好在一个环里,并且环的权值和最小……问最小权值和。

思路:没有思路,不知道怎么处理环的问题。于是去群里问了下。正确做法是拆点

如果有一条边i->j,那么就连一条i->j’的边。

正确性:

对于满足条件的环,每个点的入度和出度均为1,我们可以把每个点拆成入点和出点,那么也就是说一个入点对应一个出点,反之亦然,那么这个问题就变成了一个二分图匹配问题,

 

然后这道题有重边,2A.

又一次体会到了拆点的神奇。。。这个大概算是需要慢慢积累的技巧吧。。像辅助线一样的。。。

还有体会到了环的模型竟然也可以转化成二分图匹配,真是厉害==

 

poj 2926 Requirements (五维曼哈顿距离变换【拆点】)

http://poj.org/problem?id=2926
题意:给出n(1E5)个五维空间内的坐标…问最远的两个点距离多少。
思路:拆点即可。去绝对值。可以由二维空间推广到k维空间。一个点可以拆成2^(k-1)个点。 具体见代码。

hdu 5626 Clarke and points (曼哈顿距离变换,拆点)

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626

题意:给出n(1E6)个点的二维坐标,问距离最远的两个点的距离是多少。

思路:对曼哈顿距离进行变换。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

然后分别对x,y排序即可..最大的距离一定是y[n-1]-y[0]或者x[n-1]-x[0]

 

 

bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 (曼哈顿距离的转化【拆点】+set+并查集)

http://www.lydsy.com/JudgeOnline/problem.php?id=1604
题意:了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l≤Xi,Yi≤[1..10^9];Xi,Yi∈整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:
1.两只奶牛的曼哈顿距离不超过C(1≤C≤10^9),即lXi – xil+IYi – Yil≤C.
2.两只奶牛有共同的邻居.即,存在一只奶牛k,使i与k,j与k均同属一个群.
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

思路:一开始并没有什么思路…入手点是关于曼哈顿距离的转化。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

引用自:http://blog.csdn.net/wzq_QwQ/article/details/47746091

 

这样就有思路了。如果两个点属于同一个群,那么必须这两个点的x的差在c范围内,并且两个点的y的差也在范围内。 我们可以先按照一个 坐标排序,不妨以x为关键字排序,然后维护一段点的序列,使得这段序列中的所有的点的横坐标(其实就是最大减去最小)的差都在c范围内。然后对于序列中的所有点,我们想要知道有没有群“接纳”最新加入的点,二分找到比当前新加入点的纵坐标大的最小值和比当前新加入点的纵坐标小的最大值(set的lower_bound 第一次用),判断是否满足纵坐标的差在c的范围内。如果是,则用并差集合合并一下。

用multiset的原因是经过变换后点的坐标可能重复,以及multiset删除元素的时候不能直接删,因为会把所有相同的值删掉。

 

重要的话再说一遍:这道题最关键也是最大的收货就是,关于曼哈顿距离的变换。