最小割

51Nod 1499 图

Posted on

emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。 题意: 有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。 两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。 思路: 题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。 而跟二分图相关的只有网络流了,将图分为两半是割的概念,当然只存在最小割,正面去想的话,就是总权值和-最小割。 然后……思路就断了,找不到有效的建图方法。 可以先这么想,我们假定与源点相连的点集为相连增加权值的集合,并称之为,与汇点相连的点集则相反,称之为汇点集。 那么我们先将每个点都与 […]

强联通分量

CodeForces 864F Cities Excursions

Posted on

对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。 题意: 给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。 思路: 首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。 但是值得注意的是,点数比较少,只有$3000$个,假如我们固定起点,遍历全图来获得路径,在遍历的同时,对每一个点来记录答案。理想复杂度为$O(N^2)$,时间上满足条件。 一个问题是如何保证字典序最小,emmmm 用vector记录整张图,对于每个点的边进行排序,因为每个点访问一次,解决之。 这题还有一个合理的大坑,如果在遍历的时候,在之前已经出现了一个环,那么之后的所有点就都不会被访问。 当然你不能在找到一个环后,后面的点就不再遍历,这样会使最小字典树发生变化,会导致错误答案。 好题啊。 […]

宅技术

OwnCloud 作为图床的简易使用方法

Posted on

今天因为薛昊买VPS了,赚点访问量简单写一下吧。 OwnCloud是开源私有云软件,功能强大,作为图床只是其一个小用法。 我的ACM模板和一些很重要的文件都在上面,在本地与云服务器中都有保存。 DigtalOcean的官方论坛上的关于安装OwnCloud的文章不错,是安装教程的不二选择。传送门 以下是标题相关正文,假设你已经搭建完成 新建一个文件夹,并对其分享。这个文件夹作为我们的图床目录。 在浏览器中打开分享目录。右击图片,点击复制下载链接。 2017-10-28 17:44:53 星期六 更新,mmp,owncloud改了??? 换一个方法,得到分享目录地址后,在后面加上download?path=%2F&files=image.png 即可。 files=后面的是图片文件名 该链接就是可以用markdown,html或者其他显示出来的链接。 就这么简单。 但是在不安装插件的情 […]

心情随笔

悲伤的故事

Posted on

今天老友跟女神走一路,赶着上课的时候老友喊了我一声。 我回头看了一眼,因为要迟到了就没回应。 老友后来跟我说,女神问她 “你刚刚喊的人是谁啊” 完。

区间DP

POJ 1991 Turning in Homework

Posted on

/doge薛昊老是偷我题做,最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有,这个区间DP的套路我还真没碰到过。 这是一个大区间推小区间的套路。 题意: 小明要在某层楼的各个老师那里交一大堆作业,但是小明来早了,老师还没上班,他站在这层楼的最左边,告诉你每个老师的上班时间,最后要在某个给定位置下楼,问最少时间。 思路: shit,完全是看博客,看代码敲的。 一个比较困难的点在于给定离开地点,算了,不装了,就算取消这个条件我也写不来…… 明确可以用dp求解,首先按照位置优先开门顺序次优的顺序排序,设三维数组 $dp[l][r][k]$。 当 $k=0$ 时,表示只有 $(l,r] $ 区间内的作业没有交。 而 $k=1$ 时,表示只有 $[l,r) $ 区间内的作业没有交。 而我们的其实状态$dp[1][n][0/1]$是已知的,我们完全可以由此不断向内挤压求出小区间的结果。 […]

宅技术

ShadowSocks-Qt5 崩溃解决记录

Posted on

自从把Linux强制全局代理很长时间了,已经不知道怎么改回去了…… 结果今天ShadowSocks-Qt5 崩溃就GG了,除了让终端unset意外,其他就没有上网办法了。 因为本人使用的 Arch ,各种软件包更新的快,要是等到作者来解决这个问题可能要等很长时间…… 终端错误提醒 ss-qt5: error while loading shared libraries: libbotan-2.so.2: cannot open shared object file: No such file or directory 找了一下的确没有。 sudo find / -name "*libbotan*" [sudo] password for key: find: ‘/run/user/1000/gvfs’: Permission denied /usr/lib/libbotan-2.so /u […]

最小割

HihoCoder 1252 Kejin Game

Posted on

网络流建图神题!!! 同时也是2015年北京现场赛的金牌题,虽然我不可能去挑战金牌,但是也只有做这种神题,尽管不是自己想得,但A了之后仍然充满了满足。 题意: 给你一个DAG,表示一个游戏的技能树,也就是说某一些技能存在前置技能,但实际上这是为氪金大佬准备的游戏,有钱是真的可以为所欲为的,大佬们可以选择花钱直接无视所有前置技能直接习得某一个技能,也可以消除掉两个技能之间的依赖关系。 现在某个节俭的大佬想要学某一个技能,问最小花费。 思路: 说实话这道题一眼真的很容易想到图上DP,但是存在可以消除一个依赖的权利,使得DP存在后效性。 正解是最小割建模,这个最小割建模真的是非常巧妙: 拆点建图,u -> u' 的容量是直接氪金习得这一技能的花费 如果u,v存在依赖关系 u -> v ,建边 u' -> v ,容量为消除这个依赖的费用 将源点与每一个技能连边,容量为按技能树学习 […]