文档章节

模拟费用流

o
 osc_gu9d45li
发布于 2019/04/03 16:28
字数 3031
阅读 15
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

模拟费用流

一些感受

这个东西好神仙啊.jpg

$Orz \ \ \ laofu$

注意事项:本文代码不保证正确性,带有头文件的是正确的

一组套题

给你$n$个老鼠,$m$个洞,求一个满足要求的匹配的代价。

一个简单的部分

  • 满足,洞的容量为$1$,老鼠不能分身,代价为距离,求最小代价。

Pro 1

拥有一个限制:只能向左走。

直接排序即可。

Pro 2

无限制。

一种针对这种问题的$O(n)$解法

显然可以给出DP方程:$f[i][j]$表示,前$i$个位置,有 $ j $ 个洞需要匹配,其中$j$可以为负,表示的意义为有$-j$个老鼠需要匹配。

显然,这个一种常见的思路是将每一个距离拆开看,为$|x_i-y_j|$。

由于在匹配过程中,交叉匹配一定会有不比它差的非交叉匹配方案,所以我们将所有的交叉匹配方式去掉。

  • 对于老鼠:$j\ge 0,f[i][j]=f[i-1][j+1]+x[i],j< 0,f[i][j]=f[i-1][j+1]-x[i]$,因为所有老鼠都需要进入洞中,所以没有决策。
  • 对于洞:$j> 0,f[i][j]=\min ( f[i-1][j-1]-y[i] ,f[i-1][j]),j\le 0,f[i][j]=f[i-1][j-1]+y[i]$显然,对于后者,因为满足$y[i]$单调递增,所以必定为直接转移最优 。

但是,显然这样转移是没有办法优化掉的,是满的$n^2$,所以我们考虑如何通过分析性质将其优化掉。

  • 对于洞的优化:显然,对于决策$j>0$时,满足直接转移更小,因为$y[i]$一定会比$y[i-1]$大所以可以直接用现在的$y[i]$来替换当时的$y[i-1]$就可以变得更优,但是考虑到所有老鼠需要完全匹配,所每次只需要维护$f[i][0]$的答案即可,其他的必定会直接转移最优。

现在我们发现,对于上述DP方程,仅有直接覆盖决策和区间抬升。

简易代码如下:

stack sz,sf;
int tag1=0,tag2=0,f0=0;
for(int i=1;i<=n;i++)
{
    if(op[i]==1)//洞
    {
        tag1-=a[i],tag2+=a[i];
        sf.push(f0+a[i]-tag2);
        f0=min(sz.top()+tag1-a[i],f0);sz.pop();
    }else // 鼠
    {
        tag1+=a[i],tag2-=a[i];
        sz.push(f0+a[i]-tag1);
        f0=sf.top()+tag2-a[i];sf.pop();
    }
}
一个更加具有普适性的$O(n\log n)$解法

显然,对于这种匹配问题,一定不会存在匹配交叉的情况,所以我们考虑在此的基础上进行贪心。

对于上述DP方程,我们给出如下差分结果:

$\begin{cases} d[i][j]=f[i][j]-f[i][j-1] , j>0 \ d[i][j]=f[i][j]-f[i][j+1],j<0\end{cases}$

那么给出如下转移,由于我们发现,通过上述表达,只能表达出$f[i][j]$之间的关系,无法准确的表达出$f[i][j]$,所以我们需要维护一个$f[i][0]$来得到所以的关系。

那么给出转移:

  • 对于老鼠:$f[i][0]=f[i-1][0]+d[i-1][1]+a[i],d[i][j]=\begin{cases}d[i-1][j+1] , j>0||j<-1\-d[i-1][1]-x[i]\times 2\end{cases}$

  • 对于洞:$f[i][0]=\min(f[i-1][0],f[i-1][0]+d[i-1][-1]+a[i])$

    拆开看:

    • 如果$d[i-1][-1]+a[i]<0$:$f[i][0]=f[i-1][0]+d[i-1][-1]+a[i],d[i][j]=\begin{cases}d[i-1][j-1],j>1||j<0 \-d[i][-1]-y[i]\times 2 \end{cases}$
    • 否则:$f[i][0]=f[i-1][0],d[i][j]=\begin{cases}d[i-1][j-1],j>1||j<0 \y[i] \end{cases}$

这个东西显然就可以用上面的那个栈的做法用差分意义理解了...

有这个东西,可以发现这个DP是具有凸性的,也就是说,对于这个DP来说,$d[i][j]$在$j>0$时单调递增,在$j<0$时单调递减。

所以直接用堆来维护一下最小的$d[i][j],j>0$和最小的$d[i][j],j<0$即可。

实现代码如下:

priority_queue<int>q0,q1;
for(int i=1;i<=n;i++)
    if(op[i]==1)//洞
    {
        if(q0.top()+a[i]<0)
        {
            f0=f0+q0.top()+a[i];
            q1.push(-q0.top()-a[i]*2);
            q0.pop();
        }else q1.push(-a[i]);
    }else // 鼠
    {
        f0=f0+q1.top()+a[i];
        q0.push(-q1.top()-a[i]*2);
        q1.pop();
    }

另外的一种分析方式:

对于当前的两个堆,分别相当于是对于鼠和对于洞的匹配集合,每次强制老鼠匹配一个尚未匹配的,在他左边的洞,然后可以在之后的操作中将这次匹配反悔,变成匹配之后的某一个洞。

Pro 3

现在,对于给定问题,老鼠只能向左走,并且代价为$ x_i-y_j+w_j $,不一定每个老鼠都进入洞中,求最大代价。

好像这个题可以随便做的样子...

直接按照$a_i$从左到右的顺序,维护一个对于洞的堆,其中的比较关键字是按照$w_j-y_j$从大到小排序。

然后每次取出堆顶进行匹配即可...

一个加强之后的部分

Pro 4

对于每个洞,有一个容量限制,也就是每个洞可以容纳$b_i$个老鼠。

  • 一个弱智举了手:如果$\sum\limits_{i=1}^nb_i\le 10^6$我会!拆开每个洞然后进行Pro 2即可!
  • (看待弱智的眼神

好的,我们接下来考虑这个题如何处理...

一个神仙的做法

只需要强制往左跑,和强制往右跑的构成的堆的交集做一发即可。

这个东西的时间复杂度显然是$O(n\log n)$的。

对此的证明:显然我不会。

我所能想到的做法

显然,只需要在维护堆的时候,传进两个参数,分别表示剩余的容量,和相应的代价,然后按照第二维维护最小值即可。

每次把对应容量减去,如果为$0$就不再压入...

大致代码:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 200005
#define ll long long
const long long inf = 1ll<<40;
struct node{int op,lim;ll x,w;}a[N];
bool cmp(const node &a,const node &b){return a.x<b.x;}
int tot,n,m;ll f0,sum;
priority_queue<pair<ll ,int > ,vector<pair<ll ,int > > ,greater<pair<ll ,int > > >q1;
priority_queue<ll ,vector<ll > ,greater<ll > >q0;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),a[i]=(node){0,0,x,0};tot=n;
	for(int i=1;i<=m;i++)tot++,scanf("%lld%lld%d",&a[tot].x,&a[tot].w,&a[tot].lim),a[tot].op=1,sum+=a[tot].lim;
	a[++tot]=(node){1,n,-inf,0};a[++tot]=(node){1,n,inf,0};
	if(sum<n)return puts("-1"),0;sort(a+1,a+tot+1,cmp);
	for(int i=1;i<=tot;i++)
		if(a[i].op==1)//洞
		{
			int t=a[i].lim;
			while(!q0.empty()&&t&&q0.top()+a[i].x<0)
			{
				f0=f0+q0.top()+a[i].x;
				q1.push(make_pair(-q0.top()-a[i].x*2,1));
				q0.pop();t--;
			}
			if(t)q1.push(make_pair(-a[i].x,t));
		}else // 鼠
		{
			pair<ll ,int > tmp=q1.top();q1.pop();
			f0=f0+tmp.first+a[i].x;
			q0.push(-tmp.first-a[i].x*2);tmp.second--;
			if(tmp.second)q1.push(tmp);
		}
	printf("%lld\n",f0);
}

Pro 5

每个老鼠可以无限分身,但是分出来的身一定要进入洞中,每个洞有一个容量无限,但是至少有一只老鼠。

  • 暴力大家都会(真的吗?

然后似乎正解也不是很难,我们只需要这样考虑,对于每个老鼠的权值,分成两类,一部分,容量为$1$,费用为$-\infty+d[i][1]+x_i\times 2$,一部分容量为$\infty$,费用为$d[i][1]+x[i]\times 2$

然后对于每个洞,也就同样,当做Pro4中容量上限为$\infty$来做。

然后我们考虑到,两个容量$\infty$之间匹配,一定不优,所以不存在这种匹配情况。

大致代码:

priority_queue<pair<int ,int > >q0,q1;
for(int i=1;i<=n;i++)
    if(op[i]==1)//洞
    {
        pair<int ,int >tmp;tmp=q0.top();q0.pop();
        if(tmp.first+a[i]-inf<0)
        {
            f0=f0+tmp.first+a[i];
            q1.push(make_pair(tmp.first,1));tmp.second--;
            if(!tmp.second)tmp=q0.top();
        }else q1.push(make_pair(a[i]-inf,1));
        while(tmp.first+a[i]<0)
        {
            f0=f0+tmp.first+a[i];q0.pop();
            q1.push(make_pair(-tmp.first-a[i]*2,1));tmp.second--;
            if(tmp.second)q0.push(tmp);
        }
        q1.push(a[i],inf);
    }else // 鼠
    {
        pair<int ,int >tmp;tmp=q1.top();q1.pop();
        if(tmp.first+a[i]-inf<0)
        {
            f0=f0+tmp.first+a[i];
            q0.push(make_pair(tmp.first,1));tmp.second--;
            if(!tmp.second)tmp=q1.top();
        }else q0.push(make_pair(a[i]-inf,1));
        while(tmp.first+a[i]<0)
        {
            f0=f0+tmp.first+a[i];q1.pop();
            q0.push(make_pair(-tmp.first-a[i]*2,1));tmp.second--;
            if(tmp.second)q1.push(tmp);
        }
        q0.push(a[i],inf);
    }

pro 6

在最基础的模型上增加,每个洞有一个权值$w_i$,老鼠进洞的代价变为:$|x_i-y_i|+w_i$

想明白了,也不是很难。

只需要考虑到上述式子在不同情况下,代价不同,分别是$w_i-y_i$和$w_i+y_i$,然后分别作为洞和老鼠的反悔情况。

这样的意义代表着,老鼠即使匹配了右侧的一个洞,也可能会反悔去匹配更右侧的一个洞,因为这样可能代价更小。

其他的东西倒是没啥区别。

简易代码如下:

priority_queue<int>q0,q1;
for(int i=1;i<=n;i++)
    if(op[i]==1)//洞
    {
        if(q0.top()+a[i]+w[i]<0)
        {
            f0=f0+q0.top()+a[i]+w[i];
            q1.push(-q0.top()-a[i]*2);
            q0.pop();
            q0.push(-a[i]-w[i]);
        }else q1.push(-a[i]+w[i]);
    }else // 鼠
    {
        f0=f0+q1.top()+a[i];
        q0.push(-q1.top()-a[i]*2);
        q1.pop();
    }

pro 7

我们可以考虑,如果模型转化到树上了,如何解决。

(可能大概这个题可以被一眼秒掉了。

直接把堆换成可并堆,同样,它也不能交叉匹配,这里的交叉匹配是指在同一条链上时,两者交叉匹配。

没有简易代码

pro 8 UER8 T2 雪灾与外卖

题目链接

其实还是最基础的模型,上面加上了容量和额外代价。

直接把上面Pro 6和Pro 4的做法结合起来即可。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 200005
#define ll long long
const long long inf = 1ll<<40;
struct node{int op,lim;ll x,w;}a[N];
bool cmp(const node &a,const node &b){return a.x<b.x;}
int tot,n,m;ll f0,sum;
priority_queue<pair<ll ,int > ,vector<pair<ll ,int > > ,greater<pair<ll ,int > > >q1,q0;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),a[i]=(node){0,0,x,0};tot=n;
	for(int i=1;i<=m;i++)tot++,scanf("%lld%lld%d",&a[tot].x,&a[tot].w,&a[tot].lim),a[tot].op=1,sum+=a[tot].lim;
	a[++tot]=(node){1,n,-inf,0};a[++tot]=(node){1,n,inf,0};
	if(sum<n)return puts("-1"),0;sort(a+1,a+tot+1,cmp);
	pair<ll ,int > tmp;
	for(int i=1;i<=tot;i++)
		if(a[i].op==1)//洞
		{
			int t=a[i].lim;
			while(!q0.empty()&&t&&q0.top().first+a[i].w+a[i].x<0)
			{
				tmp=q0.top();q0.pop();
				int now=min(t,tmp.second);
				f0=f0+(ll)now*(tmp.first+a[i].x+a[i].w);
				q1.push(make_pair(-tmp.first-a[i].x*2,now));
				t-=now;tmp.second-=now;if(tmp.second)q0.push(tmp);
			}
			if(a[i].lim!=t)q0.push(make_pair(-a[i].x-a[i].w,a[i].lim-t));
			if(t)q1.push(make_pair(-a[i].x+a[i].w,t));
		}else // 鼠
		{
			tmp=q1.top();q1.pop();
			f0=f0+tmp.first+a[i].x;
			q0.push(make_pair(-tmp.first-a[i].x*2,1));tmp.second--;
			if(tmp.second)q1.push(tmp);
		}
	printf("%lld\n",f0);
}

pro 9

没看懂这题在说些啥

pro 10

给一个序列,要求选出$K$个区间,每个区间不相交,求最大和。

直接线段树维护区间连续最大值,每次区间取相反数即可。

pro 11

看样子像是Pro 9 + Pro 10的合体,反正不太可写...

预估代码会和蜀道难有一拼了.jpg

pro 12 NOI 2017 D2T2 蔬菜

题目链接

暴力的话,费用流直接建图应该有$40\sim60$分不等,我不知道我自己哪里写挂掉了,wa了好几个点...

由于我们发现,随着天数的增加,选择的蔬菜的集合只会变成原先的父集,也就是不会退流,所以直接使用线段树维护增广的合法性即可,剩下的就是堆+贪心了。

pro 13

有一棵$n $个点的树,$m$个人站在树根。每条边有一个边权。现在每个人都可以任意行走,经过一条边就要付出对应边权的代价。问最小代价使得每条边至少被一个人经过。$n \le 10^5,m \le 50$。

直接DP不解释。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【CF280D】 k-Maximum Subsequence Sum ,线段树模拟费用流

昨天考试被教育了一波。为了学习一下$T3$的科技,我就找到了这个远古时期的$cf$题(虽然最后$T3$还是不会写吧$QAQ$) 顾名思义,这个题目其实可以建成一个费用流的模型。我们用流量来限制区间...

osc_n2j4ak5s
2019/02/17
2
0
bzoj 4849: [Neerc2016]Mole Tunnels【模拟费用流】

参考:https://www.cnblogs.com/CQzhangyu/p/6952371.html费用流很简单,考虑但是会T。考虑费用流的本质,流一次需要要找一个能够从当前点到达的距离最小的点x,然后进行增广,然后把c[x]-1,...

osc_mervd488
2018/04/23
3
0
bzoj2040 [2009国家集训队]拯救Protoss的故乡

题目描述 题解: 大意是$0$为源,所有叶子节点为汇,求费用在$m$以内的最大流。 直接跑网络流会$T$。 考虑树形$dp$,发现自己不会。 考虑贪心,每次找一个路径总费用最小的叶子结点(每条边费...

osc_vy694i16
2019/02/22
2
0
zkw费用流

zkw费用流学习笔记 根据OI业界潜规则,出网络流题目时候,最大流不能卡 dinic ,费用流不能卡 ek ,但是我今天做了一道 [SDOI2009]最优图像 把我惊到了,反正就是把费用流的 ek 算法给卡了,...

osc_bm1l5rx8
2019/03/01
4
0
uoj455 【UER #8】雪灾与外卖

http://uoj.ac/problem/455 题解: https://blog.csdn.net/litble/article/details/88410435 https://www.mina.moe/archives/11762 以下是我瞎bb的: 如果我没看错的话,这个模拟费用流模拟的......

osc_thcjzdd1
2019/04/16
1
0

没有更多内容

加载失败,请刷新页面

加载更多

263. Ugly Number

题目: 263. Ugly Number 题目地址:https://leetcode.com/problems/ugly-number/ Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers......

JiaMing
14分钟前
34
0
HCIA_ARP01

ARP(地址解析协议) eNSP 常用路由器:AR2220 常用交换机:S5700、S3700 常用终端:PC、MCS(主播服务器) 设备连线:Copper(以太网用到的双绞线)、Serial(串口线,2SA接口)、Auto(自动连...

创业789
17分钟前
13
0
如何在Rails 4中使用问题 - How to use concerns in Rails 4

问题: The default Rails 4 project generator now creates the directory "concerns" under controllers and models. 默认的Rails 4项目生成器现在在控制器和模型下创建目录“Concer”。 ......

fyin1314
21分钟前
19
0
【LeetCode】 57 括号生成

题目: 解题思路: https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/ 代码: import java.util.ArrayList;import java.util.List;publ......

JaneRoad
昨天
8
0
度小满上线“推有钱”贷款推广平台,合伙人直推佣金为贷款金额的2.5%

来源 | 镭射财经 作者 | 黄老邪 2020年,蓬勃发展的消金行业受到新冠肺炎疫情的冲击,用户增长放缓、逾期率上升成为共性问题。但疫情或许只是导火索,对于消金行业来说,用户增长红利的消退,...

镭射财经
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部