最大流

POJ 1149 PIGS

Posted on

本来在学校新搞的vj上挂了一套网络流的题打算大刷特刷,突然发现还有两天就考毛概了……然而我又一点也没看……不得不先把它放下。 是昨天考完开始看这题的……想了大概3个小时,否定了很多想法,然后就没去想了……因为据说是比较经典的构图题,本来还想自己想出来的,结果今天还是没办法去看了题解,顺便发现了个好东西。 网络流建模汇总 不得不说这道题的构图思路真是巧妙,而且我自己的想法与题解的想法真的已经十分接近了…… 十分建议在看题解之前好好思考构图。 题意: 有n个人买猪,总共有m个猪圈,每个人只能去特定的猪圈买猪,按照给定顺序买,在每次购买之后管理员都可以自由调整这位顾客所能购买的猪圈里的剩下的猪,以便使得卖出的猪最多。问最多能卖多少。 思路: 先放可行思路 + 每个顾客分别用一个结点来表示。 + 对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多 […]

最大流

HDU 3572 Task Schedule

Posted on

网络流复习计划第四题,前几天在复习全国公认挂科率最高的数电,所以一直没做题。 扯一个,数电最后没复习好正打算放弃的时候被老友傻炮拉了一把。应该可以过。 题意: 给你很多任务,每个任务都需要一台机器花费给定的时间才能完成,并且限定了每个任务的完成时间区间( 比如说 [a,b] 在第a天开始,在第b天之前完成,包括b),一台机器一天只能执行一个任务,有多台机器。问你是否能全部完成任务。 思路: 先歪一个……一开始我看到这题想了一下是想贪心做的,结果在写的过程中就自己 否定--更改 了好几次,结果还是没写出来。 实际上这道题是网络流建图的一道经典题,我们让每一个任务作为流量源点,将每个流量源点与其任务时间区间的每个数建边,流量为1,表示你可以在这个区间内其中任意一天使用一台机器,而每台机器将其作为汇点汇入一个超级汇点即可。 他的数据范围最大都只有500,因为要新建流量源点,所以所有节点数量不超过 […]

BFS

UVa 11624 基础BFS

Posted on

白书训练指南上的第一道基础题,因为它在搜索中引入了超级源点,所以我自己试着做了一下,真的宛如发现新大陆一般,图论的建图技巧真的是在整个图论领域都十分适用啊。 因为UVa的尿性,写完去搜一下题解,居然有很多题解都是两次 bfs ……真是笑了 题意: 一个起火的迷宫,有很多起火的地点,给你初始位置,和起火地点,你的逃跑速度和火焰蔓延速度相等,问你能否跑出迷宫,若能,输出最短时间。 思路: 网上那些两遍bfs的应该是先一遍bfs处理出火焰蔓延到每一个格子的最短时间,在自己bfs时间加个时间大小判断的限制。 然而实际上,我们溶入超级源点的思路,然所有点一起开始跑,在同一个时间内,让所有火焰先跑,并加以标记,而人则把火焰和墙壁一起处理,避而不走。 AC Code #include <algorithm> #include <cmath> #include <cstdio […]

最大流

POJ 2455 Secret Milking Machine

Posted on

网络流复习计划第三题 传送门 啊,这道题的建图完全是自己想的,虽然花的时间比较长,但是还是算是1A了(交了第一发忘记删了文件输入……),老实说,A的有点意外呀…… 题意: 小气的农场主发现了个大宝贝并把他藏在了n点,他家在1点,总共n个点有若干条路,谨慎的农场主怕自己的宝贝被偷走,于是要从家里出发,结点不重复的走到大宝贝t次。问你在农场主所走的路径中最长的两点距离最短为多少。 思路: 当然还是二分啦! 先是建立距离图。再二分距离,再额外建图,若两点距离小于等于二分值 limit ,则建立双向建边,流量均为 1 。再跑一次dinic,如果总流量大于等于 t ,说明这个limit是满足条件的,我们再尝试缩小它,否则,增大它。 注意: 此题存在重边,存在重边的图,必须用邻接表存储。为什么来着,突然忘了,以后再补 //wordpress的markdown插件有个bug,代码太长的话头文件就显示不了 […]

最大流

POJ 2112 Optimal Milking

Posted on

网络流复习计划第二题 传送门 题意: 一个不负责任的地主有很多奶牛,他让奶牛们自己去产奶机器那里产奶,给你路径矩阵,产奶机器最多同时的奶牛是给定的,要你使走得最远的奶牛距离最短。 思路: 这题建边应该是我到现在写得比较妙的建图了。先是用flyod求出任意两个点的最短距离。(其实我们最主要想求的是每头奶牛与每台机器的最短距离)。然后我们二分这个距离区间,如下建边 1. 对于每头奶牛对于每台机器最短距离小于等于我们的二分值limit ,则建边,流量为 1 。 2. 建立超级源点,使得超级源点到每头牛的流量为 1 。 3. 建立超级汇点,使得每台机器到超级汇点的流量为 m。 每次二分跑一遍dinic,如果流量等于牛的数量,则可以缩短距离。 注: 这道题值得注意的坑点有 + 结点数已改,应该是在1000以上 + 距离矩阵距离为0应该改成inf 给我好好读题呀!!! + k是机器数,c是奶牛数…… […]

最大流

POJ 1459 Power Network

Posted on

还有半个月不到的时间暑假集训就开始了,这点时间里我准备复习一下网络流,毕竟已经好久没写了……其实也没有写多少 传送门 题意 网络流裸题,题目写的超级烦,简单说就是发电站供电,有很多发电站,用户和线路,问你所有发电站最多同时给用户供多少电。 思路 基础网络流建边,加一个超级源点和超级汇点即可。 #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> using namespace std; const int maxn = 210; const int inf = 0x3f […]

前缀和

Karen and Coffee 前缀和区间计数

Posted on

题源 codeforces Round 816 B 题意 简单说就是给你一个大区间,每次给你一条线段,给出后线段上所有数计数 +1 询问若干个区间,问区间内大于等于给定常数k的个数有多少? 思路 扫描线可写,但是无论是数状数组和线段树写起来都非常麻烦…… 最简单的正解就是很久很久没用的前缀和累加计数 前缀和累加计数 每次给定一个区间[l,r],则ary[l]++,ary[r+1]-- 最后扫一边,累加ary[i] 即得当前下标 i 的数值。 很好理解我就不解释了 ACcode #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include < […]