爱悠闲 > 分类 >

BZOJ 第29页

BZOJ 1486 HNOI2009 最小圈 二分答案+DFS
题目大意:裸的最优比例环 直接二分答案+SPFA 这样会T 因为数据卡SPFA SPFA在负环非常小的时候会退化成Bellman-Ford 时间复杂度是O(nm) (好像是O(n*m^2)?我忘了)的 换一种方法 枚举每个点 从每个点开始DFS 只沿着能将指向的点dis减小的边搜索 搜到栈中的点就返回true 期望复杂度O(n^2) 最坏复杂度O(2^n) 这种东西能过我也是醉了- - #incl
BZOJ 2400 Optimal Marks 最小割
题目大意:给定一个无向图,一些点有权值,其它点的权值可以自己指定,要求指定这些点的权值,使每条边两边的点权异或值之和最小 在此基础上要求点权和最小 首先不考虑点权和最小这个条件 那么我们将每一位分开计算 我们会发现这是一个最小割的模型 令S集为0,T集为1,如果这个点的点权已经指定,则向相应集合连流量为INF的边 每条边的两端点之间连一条流量为1的边 跑最小割就是答案 现在我们将点权考虑进去 将原
BZOJ 1266 AHOI2006 上学路线route Floyd+最小割
题目大意:给定一张图,每条边有一个长度和一个花费,要求删掉一些边使1到n的最短路变长,求最小花销 首先求出最短路(用什么求随便,反正数据范围小),然后将所有在最短路上的边连到新图中,求最小割就是答案 图没有重边- - 数组开小WA了半篇- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>
BZOJ 1601 Usaco2008 Oct 灌水 Prim
题目大意:给定n个点,每个点可以花w[i]的代价建水井,或者花p[i][j]的代价连接到一个已经供水的点,求最小花销 将每个点向超级源连一条边,边权为w[i] 求最小生成树即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 310 using namespace std
BZOJ 3218 a + b Problem 可持久化线段树+最小割
题目大意:。。。自己看 从源点出发,分别向汇点连两条流量为a和b的边,跑最大流即是a+b。 代码: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 10 #define S 1 #define T 2 #define INF 0x3f3f3f3f using namesp
BZOJ 2460 BeiJing2011 元素 贪心+高斯消元
题目大意:给定一些元素,每个元素有两个值a和b,现在需要选出一些元素,在不存在a值异或和为0的子集的情况下使b之和最大 可以用拟阵证明贪心的正确性(我不会证,同学会) 于是我们将b值排序,从大到小插入 动态维护线性基即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1
BZOJ 1845 Cqoi2005 三角形面积并 扫描线
题目大意:给定n个三角形,求面积并 n<=100 经典的扫描线 首先求出所有直线交点的横坐标,排序,去重 然后对于每个横坐标,两段之间夹的部分一定是一个或多个梯形 因此我们取中位线,求出中位线被所有三角形覆盖区间的区间并的长度,即可计算出这部分的面积 这些东西都能YY出来- - 主要东西都看代码吧- - 希望能看懂- - 我无力叙述了- - 之前求直线被三角形截取部分长度的方法是有BUG的- -
BZOJ 1023 SHOI2008 cactus仙人掌图 仙人掌DP
题目大意:给定一棵仙人掌,求这棵仙人掌的直径 首先Tarjan缩点双,开vector或者链表记录每个点属于哪些点双,以及每个点双中有哪些点 有些点双可能不是环,我们可以补上一条边看成环,无伤大雅 每次DP时,首先枚举环的根节点以外的点,对这些点所在的其它点双DP一遍 然后令f[x]为以x为根的子仙人掌的所有点和x之间的最大距离 然后我们将环倍增 用单调队列来更新答案 保证决策点和被更新点的距离不超
BZOJ 2127 happiness 最小割
题目大意:给定一个座位图,相邻两人之间是朋友,每个人选择学文或学理会有相应的喜悦值,一对朋友同时选择学文/学理也会有相应的喜悦值,求喜悦值之和最大的方案 这个题的模型显然是最小割- - 看到矩阵上相邻点之间的关系 很容易想到黑白染色 随后就能想到将某种颜色的点源汇对调 但是很可惜我没建出图来- - 自己YY了一种做法 但是喜闻乐见地发现建图方法不对- - 还是OTZ HZWER一下吧- - htt
BZOJ 2039 2009国家集训队 employ人员雇佣 最小割
题目大意:给定n个人,每个人有一个佣金,i和j如果同时被雇佣会产生2*E(i,j)的效益,i和j如果一个被雇佣一个不被雇佣会产生E(i,j)的亏损,求最大收益 首先对于每一个cost[i],从点i出发向汇点连一条流量为cost[i]的边 对于每一对点(i,j),建图如下: 从S向点i和点j各连一条流量为E(i,j)的边 i和j之间连一条流量为2*E(i,j)的双向边 这样可以保证每种割法对应一种雇