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

本文共 5454 字,大约阅读时间需要 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 导航噩梦

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.36.148.57]2022年08月05日 09时35分48秒

关于作者

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

最新文章

npm : 无法加载文件 D:\nodejs\npm.ps1,因为在此系统上禁止运行脚本。 2021-05-20
React-umi-antd在菜单栏上编辑(添加按钮) 2021-05-20
react使用echarts完整细节实例(后台数据渲染&&布局实现) 2021-05-20
antd-select下拉框同时获取所选值id和名字属性 2021-05-20
antd-select选择框联动(后台数据)解决 2021-05-20
React-antd日期选择框日期初始化问题(invalid date)解决 2021-05-20
ant-design表格序号分页连续自增设置 2021-05-20
react-ant-design动态渲染可滑动表格组件 2021-05-20
react-dva-ant-design-pro在编辑侧边菜单栏(添加徽标) 2021-05-20
Ant Design的DatePicker组件禁用日期选择范围(结束日期大于开始日期)禁用状态 2021-05-20
设置文本省略号移入显示布局不变完整完美解决方案 2019-03-17 10:06:26
URL跳转错误之 URL特殊字符转义 2019-03-17 10:06:25
ant-design-pro表格多选操作后还会默认勾选的解决办法 2019-03-17 10:06:24
CSS3 filter(滤镜) 制作图片高斯模糊无需JS 2019-03-17 10:06:24
react-ant-design中用到的数组遍历迭代方法forEach和map方法案例区分说明 2019-03-17 10:06:23
react-ant-design实现Modal输入框实现联想输入 2019-03-17 10:06:22
react-ant-design带有下拉框选择的搜索功能实现详解(表格组件的使用) 2019-03-17 10:06:22
react-ant-design表格组件列表数据渲染 2019-03-17 10:06:21
react-ant-design组件封装抽取之表格页面封装举例(组件封装方法) 2019-03-17 10:06:20
react-ant-design 携带id进行页面跳转 2019-03-17 10:06:20