题意： • 一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划，使总的花费最小。编程任务：编程找出一个最佳餐巾使用计划. 题解： 这个题解讲的真不错• 给每天建两个...

Codeforces1437 E. Make It Increasing（LIS）  题意：  你有一个长度为n的数列a和一个含有k个不同整数的集合b，b中的数都在[1,n]内。 现在你可以进行一些操作，每次操作中你可以选择两个数i和x，并将x赋值给ai。其中1<=i<=n，但i不能出现在集合b中，而x可为任意整数。 求出将数列a变为严格上升序列的最小操作次数。  题解：  首先实现严格递增是比较难处理的，我们可以通过a[i]=a[i]-1，问题就变成非严格递增 因为有k个位置不能改变，如果这k个位置并非严格递增，那题目无解。也就是a[b[i]]>a[b[i+1]] 如果有解...

题目描述：  题解： 看了很多题解，无论什么解法都绕不开分层图在本题中加满油的车每次可以移动K步，那么我们就可以建立一个K+1层的分层图，表示汽车油量k的状态（油量0...k），然后根据题目要求建图首先我们规定(k从1开始)第k层第i行第j列点编号为(k-1) * n * n + (i-1) * n + j首先我们从第k层(i,j)建立一条边到第k+1层(i,j),边权为0，相当于车原地不动（其实这一步可有可无）然后肯定是否到达油站来详细分析：当到达油站时，油会加满，所以无论当前为哪一层都要指向第一层指向一个边，边权为a（即加油费）。然后从第一层的(i,j)向第二层的四个方向指向边，因为当i和...

题意： 约翰一共有 N 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 1 出发到牧场 N 去给奶牛检查身体。 通过每条小径都需要消耗一定的时间。约翰打算升级其中 K 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。 请帮助约翰决定对哪些小径进行升级，使他每天从 1 号牧场到第 N 号牧场所花的时间最短。 题解： 参考题解“”一直知道分层图，但是没用过，突然遇到一道分层图的网络流题目，发现自己忘了分层图咋实现，赶紧拿来一道分层图模板题做做简单说说什么是分层图：其实就是将一个平面的图重新建图，有好几层具体的说每层图之间各自...

[ZJOI2010]网络扩容[网络流24题] 题意： 给定一张有向图，每条边都有一个容量 c 和一个扩容费用 w。这里扩容费用是指将容量扩大 1 所需的费用。求：  在不扩容的情况下，1 到 n 的最大流； 将 1 到 n 的最大流增加 k 所需的最小扩容费用 题解： 第一问好说就是跑最大流，关键是第二问怎么想两个方法：其实本质也是一个，我们可以将扩容的费用转化为增加一点流量，花费W的费用，因为我们要让费用尽可能低，所以问题就成了最小费用流的模型如何建图呢？我们可以在第一问的基础上继续建图，也可以重新建图（个人倾向第一种）如果是第一种，我们在跑完最大流后，利用残余网络继续建图，（第一问建图中每...

@[toc] 基本概念 点：平面上一点，用坐标(x,y)来表示 struct Point{ double x,y; };  向量：同时具有大小和方向的量 。把向量从原点出发到达的点的坐标作为该向量的坐标 typedef Point Vector; 点与向量的运算 点 + 向量 = 点向量 + 向量 = 向量点 - 点 = 向量向量 * k = 向量 Vector operator +(Vector a,Vector b) { return Vector(a.x+b.x,a.y+b.y); } Vector operator -(Vector a,Vector b) { return Vecto...

题意： n次顺序填数字，每次填一个[1,m]的数到当前位置，如果这个位置填的数比上一次填的数要大，形成顺序，他的兴奋度会增加1点，如果这个数比上一次填的数要小，形成逆序，他的兴奋度会增加2点，如果两个数相等，那么什么都不会发生。（如果是第一次填数，同样不会发生任何事情）已知n和m求所以填数方案的兴奋度之和结果mod 1e9+7 题解： 参考题解总是想不到。。也就不是很明白，之后再想吧。。。

题目描述 有 nn 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 cij。试设计一个将 n 件工作分配给 n 个人做的分配方案，使产生的总效益最大。 题解： 第一反应裸的二分图最优匹配最小总效益就是把边取负值求最大总效益即可网络流也可以做，先将源点S与每个人连一条容量为1，费用为0的弧，同样从每一个任务向汇点连一条容量为1，费用为0的弧然后对于每一个人和每一个任务，对应的从人向任务连一条容量为1，费用为Cij的弧，然后跑最大费用最大流和最小费用最大流就行了为什么要标记容量为1，因为设置容量是为了防止一个点被多次匹配代码都不是自己的，等日后有空补上 代码： 第一个方法： ...

题目： 假设有来自n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri, i=1,2,...,n。会议餐厅共有m张餐桌，每张餐桌可容纳ci (i=1,2,...,m)个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。编程任务：对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。• m<=150,n<=270 题解： 关键在于如何建图具体建图如下：  将源点S与每个单位链接一条流量为此单位代表数的边 将每张桌子与汇点T连一条流量为此桌子容量的边 将每个单位与每张桌子连一条流量为1的边...

NC19939 [CQOI2015]网络吞吐量 题目： • 路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。• 现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及...

NC 213820 [网络流24题]最长递增子序列问题 题目: • 给定正整数序列x1 ,...... , xn。 （1）计算其最长递增子序列的长度s。 （2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。• 编程任务：设计有效算法完成（1）（2）（3）提出的计算任务。• 1≤n≤500 题解： 参考自众多大佬题解第一问好说，经典dp问题，F[i]，表示以第i位为结尾的最长上升序列的长度第二三问是网络流问题因为题目要求是不下降序列，所以我们可以将不下降序列中的数字连边 建图方式：  我...

例2：NC213818 [网络流24题]魔术球问题 题目： • 假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。编程任务：对于给定的n，计算在n根柱子上最多能放多少个球。• 1≤n≤55 题解： 首先思想很重要，不是明显的图论，要往图论方向靠 建图方式：S与左图所有数相连，右图所有数与T相连 对于一个进来的编号的球x，有两个选择：第一个选择是放在某个和他能组成平方数的球（我...

NC51319 King's Quest 题目： N个男生和N个女生，告诉你每个男生喜欢的女生编号，然后给出一个初始匹配（这个初始匹配是一个完美匹配），求在保证匹配是完美匹配的基础上，输出每个男生可能会匹配的女生 题解： 参考题解：让我们首先来考虑建图 如果王子u喜欢妹子v那我们可以从u向v连一条有向边 如果妹子v可以与王子u配对（即在配对表上），那我们可以从v向u连一条有向边 根据样例： 4 2 1 2 2 1 2 2 2 3 2 3 4 1 2 3 4 可以得到图红的是王子，蓝的是妹子，绿的表示从王子到公主，黄的表示从妹子到王子 仔细观察我们发现了这张图的一些特别之处：紫色部分为强连通分量...

NC20099 [HNOI2012]矿场搭建 题目： • 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。• 于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。• 请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。 题解： 点双连通分量的性质：  任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性，即BCC中无割点 若BCC间有公共点，则公共点为原图的割点 无向连通图中割点一定属于至少两个BCC...