BZOJ1930 [Shoi2003]pacman 吃豆豆 费用流
发布日期:2022-02-07 06:39:34 浏览次数:16 分类:技术文章

本文共 5427 字,大约阅读时间需要 18 分钟。

题目大意:在二维平面上有若干个点,求出两条不相交的二维LIS,使得上面包含的点的数目最多。

思路1:暴力建图

注意到不相交这个条件根本没用,画图可以发现如果相交的话,我们总可以通过交换一些点使得两个序列不相交。

那么问题转化为求出两个没有公共点的上升子序列,使得长度之和最大。

对于这种情况我们利用最大费用流求解。

设(a,b)分别表示一条有向边的流量和费用。

S->S' (2,0)

S'->x(1,0),x'->T(1,0)(1<=x<=n)

x->x' (1,1) 表示加上这个点会造成1的费用,点权限制为1表示只能出现一次

p'->q(1,0)条件是p.x<=q.x&&p.y<=q.y,表示q可以出现在p的后面,也就是说1的流量能从p流过产生费用后,再流到q.

但是这样建模的最大边数可以卡到O(n^2),只能得到70分。

思路2:优化

上述建模的瓶颈在于p'->q之间的边数太多,存在大量冗余。

我们不妨考虑将所有点按照(x,y)二元组排序。

然后若两个点之间存在某一个点使得这三个点依次能够构成一个上升子序列,则这两个点之间不连边。

但是这样的话,有可能两条流量都想要经过某个点,所以我们在每个点的入点和出点之间加上一条流量为2的边,使得这两条流量可以通过。

详细的细节自己看代码。

新技能get:允许带负权边的ZKW费用流!!

Code(spfa+多路增广):

#include 
#include
#include
#include
#include
#include
#include
using namespace std; #define INF 0x3f3f3f3f #define N 2010queue
q;int Edges = 0;struct Solver { int head[N<<1], next[N*N], end[N*N], flow[N*N], cost[N*N], ind; int d[N<<1]; bool inq[N<<1], vis[N<<1]; void reset() { ind = 0; memset(head, -1, sizeof head); } void addedge(int a, int b, int _f, int _c) { int q = ind++; end[q] = b; next[q] = head[a]; head[a] = q; flow[q] = _f; cost[q] = _c; } void make(int a, int b, int _f, int _c) { addedge(a, b, _f, _c); addedge(b, a, 0, -_c); } bool spfa(int S, int T) { memset(d, -1, sizeof d); d[S] = 0; inq[S] = 1, q.push(S); int i, j; while(!q.empty()) { i = q.front(); q.pop(); inq[i] = 0; for(j = head[i]; j != -1; j = next[j]) { if (flow[j] && d[end[j]] < d[i] + cost[j]) { d[end[j]] = d[i] + cost[j]; if (!inq[end[j]]) { inq[end[j]] = 1; q.push(end[j]); } } } } return d[T] != -1; } int Getflow(int p, int S, int T, int maxflow) { if (p == T) return maxflow; vis[p] = 1; int last = maxflow; for(int j = head[p]; j != -1; j = next[j]) { if (flow[j] && d[p] + cost[j] == d[end[j]] && (end[j] == T || !vis[end[j]])) { int to = Getflow(end[j], S, T, last > flow[j] ? flow[j] : last); flow[j] -= to; flow[j ^ 1] += to; last -= to; if (!last) return maxflow; } } return maxflow - last; } int Maxcost(int S, int T) { int res = 0; while(spfa(S, T)) { memset(vis, 0, sizeof vis); res += Getflow(S, S, T, INF) * d[T]; } return res; }}G; struct Node { int x, y; void read() { scanf("%d%d", &x, &y); } bool operator < (const Node &B) const { return x < B.x || (x == B.x && y < B.y); }}S[N]; #define f(x) (x<<1)#define g(x) (x<<1^1)int main() { int n; scanf("%d", &n); register int i, j; for(i = 1; i <= n; ++i) S[i].read(); sort(S + 1, S + n + 1); G.reset(); G.make(0, 1, 2, 0); for(i = 1; i <= n; ++i) G.make(1, f(i), 1, 0), G.make(g(i), 2 * n + 2, 1, 0), G.make(f(i), g(i), 1, 1), G.make(f(i), g(i), 1, 0); for(i = 1; i <= n; ++i) { int Min = INF; for(j = i + 1; j <= n; ++j) { if (S[j].y < Min && S[j].y >= S[i].y) G.make(g(i), f(j), 2, 0); if (S[j].y >= S[i].y) Min = min(Min, S[j].y); } } printf("%d", G.Maxcost(0, 2 * n + 2)); return 0;}
Code2:ZKW费用流

#include 
#include
#include
#include
#include
#include
#include
using namespace std; #define INF 0x3f3f3f3f #define N 2010queue
q;int Edges = 0;struct Solver { int head[N<<1], next[N*N], end[N*N], flow[N*N], cost[N*N], ind; int d[N<<1], slack[N<<1], used[N<<1], id; bool inq[N<<1]; void reset() { ind = 0; id = 1; memset(used, 0, sizeof used); memset(head, -1, sizeof head); } void addedge(int a, int b, int _f, int _c) { int q = ind++; end[q] = b; next[q] = head[a]; head[a] = q; flow[q] = _f; cost[q] = _c; } void make(int a, int b, int _f, int _c) { addedge(a, b, _f, _c); addedge(b, a, 0, -_c); } void spfa(int S, int T) { memset(d, 0x3f, sizeof d); d[S] = 0; inq[S] = 1, q.push(S); int i, j; while(!q.empty()) { i = q.front(); q.pop(); inq[i] = 0; for(j = head[i]; j != -1; j = next[j]) { if (flow[j]) { if (d[end[j]] > d[i] + cost[j]) { d[end[j]] = d[i] + cost[j]; if (!inq[end[j]]) { inq[end[j]] = 1; q.push(end[j]); } } } } } for(i = S; i <= T; ++i) d[i] = d[T] - d[i]; } bool Newlabel(int S, int T) { int i, Min = INF; for(i = S; i <= T; ++i) if (used[i] != id && slack[i] < Min) Min = slack[i]; if (Min == INF) return 0; for(i = S; i <= T; ++i) if (used[i] == id) used[i] = -1, d[i] += Min; return 1; } int Getflow(int p, int T, int maxflow) { if (p == T) return maxflow; used[p] = id; for(int j = head[p]; j != -1; j = next[j]) { if (flow[j] && used[end[j]] != id && d[p] == d[end[j]] + cost[j]) { int to = Getflow(end[j], T, maxflow > flow[j] ? flow[j] : maxflow); if (to) { flow[j] -= to; flow[j ^ 1] += to; return to; } } else if (flow[j]) slack[end[j]] = min(slack[end[j]], d[end[j]] + cost[j] - d[p]); } return 0; } int Mincost(int S, int T) { int res = 0, get; spfa(S, T); do { memset(slack, 0x3f, sizeof slack); while((get = Getflow(S, T, INF))) res += get * d[S], ++id; }while(Newlabel(S, T)); return res; }}G; struct Node { int x, y; void read() { scanf("%d%d", &x, &y); } bool operator < (const Node &B) const { return x < B.x || (x == B.x && y < B.y); }}S[N]; #define f(x) (x<<1)#define g(x) (x<<1^1)int main() { int n; scanf("%d", &n); register int i, j; for(i = 1; i <= n; ++i) S[i].read(); sort(S + 1, S + n + 1); G.reset(); G.make(0, 1, 2, 0); for(i = 1; i <= n; ++i) G.make(1, f(i), 1, 0), G.make(g(i), 2 * n + 2, 1, 0), G.make(f(i), g(i), 1, -1), G.make(f(i), g(i), 1, 0); for(i = 1; i <= n; ++i) { int Min = INF; for(j = i + 1; j <= n; ++j) { if (S[j].y < Min && S[j].y >= S[i].y) G.make(g(i), f(j), 2, 0); if (S[j].y >= S[i].y) Min = min(Min, S[j].y); } } printf("%d", -G.Mincost(0, 2 * n + 2)); return 0;}

转载地址:https://blog.csdn.net/wyfcyx_forever/article/details/40583315 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:面试官最爱问的问题背后真相
下一篇:BZOJ3362 [Usaco2004 Feb]Navigation Nightmare 导航噩梦

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月17日 16时11分59秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql分组显示行号_mysql 显示行号,以及分组排序 2019-04-21
MySQL常见的主从复制架构_如何搭建经典的MySQL 主从复制架构 2019-04-21
编写python程序、计算账户余额_小明有20w存款存在余额宝中,按余额宝年收益为3.35%计算,用Python编写程序计算,多少年后小明的存款达到30w?... 2019-04-21
python 公众号引流_公众号引流方法有哪些? 2019-04-21
java 减少内存_java中减少内存占用小技巧 2019-04-21
centos 7 mysql图形界面_centos7-vnstat图形界面搭建 2019-04-21
java 防渗透_「java、工程师工作经验怎么写」-看准网 2019-04-21
java中跳出当前循环怎么做_在java中,如何跳出当前的多重循环? 2019-04-21
java程序中执行maven_java – 将一个enviornment变量传递给Maven中的已执行进程 2019-04-21
java16下载_java lombok下载 2019-04-21
python 图像处理与识别书籍_Python图像处理之识别图像中的文字(实例讲解) 2019-04-21
java安全初始化_java安全编码指南之:声明和初始化 2019-04-21
java jstat gc_分析JVM GC及内存情况的方法 2019-04-21
php pclzip.lib.php,php使用pclzip类实现文件压缩的方法(附pclzip类下载地址) 2019-04-21
php dns更新,php_mzdns: 站群,大量域名 通过 dns 服务商 api 批量添加 ip 工具。你懂的~ 基于 mzphp2 框架。... 2019-04-21
jdk 1.8 java.policy,JDK1.8 导致系统报错:java.security.InvalidKeyException:illegal Key Size 2019-04-21
php linux权限,Linux权限详细介绍 2019-04-21
典型环节的matlab仿真分析,典型环节的MATLAB仿真.doc 2019-04-21
Php contenttype类型,各种类型文件的Content Type 2019-04-21
php使用redis持久化,redis如何持久化 2019-04-21