51nod-1021-石子归并 (区间DP,四边形优化)

题目链接:1021 石子归并 题目大意: N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。 Input 第1行:N(2 <= N &l…

POJ – 3041 – Cable master (二分图匹配入门,最小顶点覆盖)

题目链接:POJ - 1064 题目大意: 有一个N*N的图,图中一些点有障碍物,有一种武器,一次可以摧毁一行或者一列的障碍物, 问最少需要多少次,能把所有障碍物清除干净。 题目分析: 对于每个坐标点,建立一个行对应列的边,然后进行二分图匹配。 已知最大匹配数=最小顶点覆盖(最小顶点覆盖要求用最少的…

POJ – 1486 – Sorting Slides (二分匹配的唯一边)

题目链接:POJ - 2594  题目大意: 故纸堆:桌上有n张幻灯片杂乱地叠在一起,给出每张幻灯片的边界和页码坐标,求在不翻动的情况下哪些页码可以确定? 页码可能在保护页码坐标的任意一张幻灯片上 题目分析: 二分图找唯一匹配的边,即删除该边之后无法形成完美匹配。 首先见图找到一个完美匹配…

POJ – 3020 – Antenna Placement (二分图最小路径覆盖)

题目链接:POJ - 3020 题目大意: 一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。 每个基站只能覆盖所在点已经他相邻的一个点(或上或左或下或右)问至少放置多少个基站才能使得所有的城市都覆盖无线? 题目分析: 这是一个二分图的最小路…

POJ – 2983 – Is the Information Reliable? (差分约束系统)

题目链接:POJ - 2983 题目大意: 有部分点之间知道具体相对位置, 有部分点仅知道一点在另一点的某边。 问是否存在这样的点集。 题目分析: 建图,差分约束系统。 注意的是,对于spfa(),要加入一个权为0的超级源点,使得图连通。 bellman-ford算法则不需要。 给出代码: #inc…

POJ – 1201 – Intervals (差分约束系统)

题目链接:POJ - 1201  题目大意:有一个序列,题目用n个整数组合 [ai,bi,ci]来描述它,[ai,bi,ci]表示在该序列中处于[ai,bi]这个区间的整数至少有ci个。如果存在这样的序列,请求出满足题目要求的最短的序列长度是多少。 题目分析: 利用差分约束转化成图的最短路…

POJ – 2492 – A Bug’s Life (种类并查集)

题目链接:POJ - 2492 题目大意: 一种动物有两种性别,假设不同性别才能进行配对, 给出配对情况,问是否存在同性配对的情况。 题目分析: 种类并查集。 用a和a+n代表两种性别。 如果a和b在一个并查集内,则同性。 给出代码: #include <cstring> #i…

POJ – 3321 – Apple Tree (树状数组,DFS序,模板)

题目链接:POJ - 3321 题目大意: 有一颗树,根永远为1. 初始状态每个节点上的值都为1 有两种操作: 查询某一节点子树上所有节点和的值 将某一节点值取非 题目分析: 利用DFS序将树转变成线性区间结构,然后利用树状数组即可。 注意:莫名奇妙的卡vector,要用 vector<vec…