IDA*

POJ 2286 The Rotation Game

Posted on

康复计划 之 ida* 题意: 这种玩具要你操作最少次数且操作字典序最小,使得中间的8个数字相同。 思路: 迭代加深 启发式 搜索 估价函数采用 8 - 中间数字最多的数字数量 因为每次操作如果想达到最终结果,一次最多只能转化出一个,如 aaab ,一次转化出两个的话,中间那个必定不相同,可以自己在纸上试试。 这道题本身在深搜层数上并不会很大,ida * 的优势就体现了出来。 AC Code #include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <vector> using namespace std; vector<int> ans; int ary[30], deep; int center[] […]

BFS

HDU 1043 Eight

Posted on

康复计划之搜索 1 因为有个小学弟在第二天就说ida * 看不懂,搞得我挺慌 我可以说我也不是很熟么 题意: 经典八数码 思路: 这里提供的是单向bfs + 打表思路,本来想复习ida * 但是不小心看到了kuangbin的思路,就写了一下。 简单说就是我从起始状态 123456780 开始对0进行bfs,通过康托展开的hash函数进行记录状态和路径。询问时对哈希值进行询问和查找。 实际上并没有用到康托展开的性质,只是通过2进制hash而已…… #include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <queue> #in […]

最大流

POJ 2391 Ombrophobic Bovines

Posted on

又是一些细节问题…… 如果以我现在的水平去现场赛写网络流的题目,就算我会建图,我觉得还是挺悬的。 这里提前简单说一下dinic算法的最低上限的情况。 dinic的最高上限是 O ( \( V^2 E \) ) ,这是谁都知道的,然而对于一些特殊的图还有一些更低的上限。 在具有单位容量的网络中,Dinic算法可以在更短的时间内输出结果。每条阻塞流可以在 O ( E ) 的时间内构建,并且阶段的数量不超过 O( \( \sqrt E \) )或 O ( \( \sqrt[3] { V ^ 2 } \) )。此时算法的复杂度为 O ( \( min { ( \sqrt E , \sqrt[3] { V ^ 2 } ) } \) E )。 在二分图匹配问题的网络中,阶段的数量不超过 O ( \( \sqrt V \) ),算法的时间复杂度不超过 O ( \( \sqrt V E \) )。这种算法 […]

最大流

POJ 1637 Sightseeing tour

Posted on

kuangbin把这道题的难度设置为 crazy …… 搞得我都不太敢刷…… 题意: 混合图中欧拉回路的判定 思路: 这道题是真的不好想,最后还是去看了题解,因为比较典型 好吧是我菜 混合图欧拉回路无法用普通的定理去判定,不行可以试试……网络流建模给出的思想是将无向边任意转化成有向边,再去通过变换无向边的方向来实现欧拉回路。 建图方式: + 对无向边建立你所设定的方向,容量为1 + 对于每个点,如果入度与出度差的绝对值为奇数,则不存在欧拉回路。 ( 因为反转一条边,则两个点的入度出度差各自变化 2 ) + 否则 ,对于每个点如果 入度>出度 则为 汇点,与超级汇点容量为 ( 入度 - 出度 ) / 2 ,反之则为源点,与超级源点容量为 ( 出度 - 入度 ) / 2 。 跑一遍dinic即可。 残余网络中流量不为0的边即为反转边。这样求出欧拉路径也不算什么难事了。 #include […]

最大流

POJ 1815 Friendship

Posted on

感觉网络流的题目总是莫名奇妙的卡在数组大小上 数组开小,既能WA,又能TLE,也真实神奇…… 题意: 给你一张图,让你求出最小割集,并按照字典序输出。 思路: 老套的思路,那些discuss里的奇淫巧计看了一下貌似全都被推翻了…… 枚举+最大流,尝试删点,如果流量减少,则为割点。 #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> //#define DEBUG1 1 using namespace std; const int maxn = 410; const i […]

最大流

SPOJ 287 Smart Network Administrator

Posted on

坑哭了…… 先是一个小地方初始化错误,tle了5发,看到下面说数据很多,还尝试开了输入挂…… 然后数组开小,WA了n发 题意: 村通网系列。一个村子只有1号家庭有网络,现在有k家用户想要通网,为了网络质量,在一条街道上的每条网络都必须是不同的网线。问最少需要多少掉网线。(差不多就是这样的,颜色什么的就别管了……) 思路: 这道题我看完第一个想法就是二分,但是因为dinic的复杂度问题不是很敢写。搜了一下题解,居然真的是二分……众所周知dinic的复杂度上限为 O(n^2 * m) 如果是稠密图,最高可达 O(n^4) 二分最多9次,除开重新建图,数据最多500组,n最多500,也就是 500^5 …… 然而结果是 0.69 ,我也不知道是什么单位,在spoj刷题是几百年前了…… ,应该是 s 吧。 AC code #include <algorithm> #include &l […]

最大流

ZOJ 2760 How Many Shortest Path

Posted on

暑假集训第一天,早上看了一下支配树,结果表示完全不会,看不懂……不得不回老本写起了网络流 题意: 给你一个距离矩阵,问你完全不重叠的最短路数目。 思路: 完全不重叠,意为每条边只能走一次,我以网络流建模,对于每条在最短路径内的边的流量设置为1,跑出来的结果即题意所求。这个很自然想得到吧 关键就在于如何判断一条边是否属于最短路径。 这里给出一种比较好的方法,对于一条边 ( u , v ) ,如果 min ( st , u ) + ( u,v ) + min ( v , en ) 等于最短路径长度,那么这条边就属于最短路径 这也是很显然的 注: 如果起点与终点相同,则直接输出inf ,本人英语不好,看了一下题意我还意淫成了 如果存在( st , en ) 就输出inf。 结果我tle了4发…… 因为一直wa我看了一下其他题解,居然有人以自环>=0为理由A不了……我感觉很奇怪。如果自环权值 […]