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

本文共 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 导航噩梦

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月17日 13时23分41秒

关于作者

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

推荐文章

java当前路径_java获取当前路径的几种方法 2019-04-21
java web传递参数_Javaweb的八种传值方式 2019-04-21
java gui支持的包有哪两个_Java GUI 2019-04-21
java list详解_java集合List解析 2019-04-21
java坐标代码_java实现计算地理坐标之间的距离 2019-04-21
kettle调用java程序_Kettle ETL调用 java代码来进行数据库的增删改查 2019-04-21
mysql 取两个时间差 php_在php和MySql中计算时间差的方法详解 2019-04-21
mysql 重启数据库实例_mysql 单机多实例重启数据库服务 2019-04-21
collator java_Java Collator getInstance(Locale)用法及代码示例 2019-04-21
dtc mysql_DTCC归来-高可用可扩展数据库架构探讨 2019-04-21
java怎样将日期本土化_Java中的日期操作 2019-04-21
java生产者消费者模型到精通_java生产者消费者模型 2019-04-21
java 执行 awk_3.1 biostar lesson3 linux学习日记;java版本;awk 2019-04-21
java二叉树求权值_百度笔试题目:二叉树路径权值和【转】 2019-04-21
欧亚马 java折叠车_如何选择欧亚马折叠车? 2019-04-21
python函数代码块以什么开头_Python初体验-开篇 代码全析 2019-04-21
java闹钟程序设计_JAVA课程设计_闹钟的设计与实现项目-报告_附源代码.doc 2019-04-21
java中的无效的列类型_java.sql.SQLException: 无效的列类型: 1111 2019-04-21
php rewrite url_PHP_URL Rewrite的设置方法,URL Rewrite需要服务器的支持! - phpStudy 2019-04-21
php读取大文件某行内容,PHP读取和修改大文件的某行内容_PHP教程 2019-04-21