UOJ #455 [UER #8]雪灾与外卖 (贪心、模拟费用流)

题目链接

http://uoj.ac/contest/47/problem/455

题解

模拟费用流，一个非常神奇的东西。
本题即为WC2019 laofu的讲课中的Problem 8，经典的老鼠进洞模型，洞有容量和额外权值。
这道题的Subtask 4,5,6,7分别对应着老鼠进洞的最基础模型、洞有额外权值、洞有容量、洞有容量和额外权值四个变形。
让我们从最简单的开始各个击破。

Subtask 4

注: 本部分配合WC2019课件里的代码图理解效果更佳。
数轴上有(n)只老鼠(坐标(x_i))和(m)个洞(坐标(y_i))，每个老鼠必须进一个洞，每个洞至多进一只老鼠，最小化距离和。
假设洞(i)匹配了老鼠(j), 则若(y_i<x_j)代价为(x_j+(-y_i)), 否则为((-x_j)+y_i)，不妨拆成(i,j)两部分分别计算。
使用可撤销贪心的策略。
维护一个老鼠堆和一个洞堆，从左到右扫描。
若当前扫到一只老鼠(i)，那么先随便匹配一个目前空闲的洞（不妨假设负无穷远处有无穷多个洞），从洞堆中取出一个元素(j)匹配，其代价为(x_i+j)
考虑当后面插入洞的时候允许老鼠反悔（像极了费用流的反向边）而匹配新的洞，那么如果一个老鼠反悔而匹配了右面的新洞(k), 那么代价的增量为((y_k-x_i)-(x_i+j)=y_k+(-2x_i-j)), 所以往老鼠堆中插入元素(-2x_i-j).
若当前扫到一个洞(j)，考虑是否有老鼠要反悔，从老鼠堆中取出一个元素(i), 若反悔的代价(y_j+i>0)那么让这个老鼠堆中的老鼠反悔，同时往洞堆中加入元素(-2y_j-i)，表示后面的老鼠再匹配这个洞的代价；否则只往洞堆中插入元素(-y_j).
时间复杂度(O(nlog n)).

Subtask 5

洞有额外权值(w)，怎么办呢？
考虑这样和原来有什么区别: 原来只有老鼠会反悔（因为不会有舍近求远故意匹配较远洞的情况），但是现在可能出现了！
解决办法：让洞和洞匹配，洞也可以反悔。
插入洞(i)时，除了往洞堆中插入元素之外，往老鼠堆也插入元素，表示该洞反悔的代价。插入的元素是(-y_i-w_i), 相当于用新洞(j)替代该洞会少这么多的代价再加上(y_j+w_j).
坑：WC课件中那个“老鼠和洞同时反悔不优”目前没看明白。

Subtask 6

洞有容量。
有一个神仙做法，见WC课件或UOJ题解。
正常做法: 往堆里存一个pair, 记录价值和剩余容量。
每次增广会使一个往左走的老鼠改为往右走，因此复杂度正确。

Subtask 7

洞有容量，也有附加权值，显然Subtask 6的做法时间复杂度错误。
但是我们发现，如果两个老鼠(i,j)分别匹配洞(k)且(x_i<x_j<y_k), 那么这两种情况下往洞堆中丢的元素是一样的，都是(-y_k-w_k).
所以我们可以“批量加入、批量增广”，这样复杂度就得到了保证。
其实这个东西就已经非常像费用流增广的过程了。
费用流的一条重要性质是: 如果不是每次选全局最短路，而是按另一顺序对和源点相连的边必须连的点进行增广，那么也是正确的。

建议结合代码以获取更好理解。

代码

代码写出来发现和费用流神相似！

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<algorithm>
#define llong long long
using namespace std;
const int N = 1e5;
const llong INF = 1000000000000ll;
struct Node
{
int w; llong c;
Node() {}
Node(int _w,llong _c) {w = _w,c = _c;}
bool operator <(const Node &arg) const {return c>arg.c;}
};
struct Element
{
llong x,w,c;
} a[N+3],b[N+3];
priority_queue<Node> mouse,hole;
int n,m;
llong ans;
void insertmouse(int x)
{
llong ret = INF;
if(!hole.empty())
{
Node tmp = hole.top();
ret = tmp.c+x;
hole.pop(); if(tmp.w-1>0) {hole.push(Node(tmp.w-1,tmp.c));}
}
ans += ret;
mouse.push(Node(1,-x-ret));
}
void inserthole(int x,int w,llong c)
{
int rst = w;
while(!mouse.empty() && rst>0)
{
Node tmp = mouse.top();
llong val = x+c+tmp.c;
if(val>=0) break;
int flow = min(rst,tmp.w);
ans += val*flow; rst -= flow;
hole.push(Node(flow,-val-x+c));
mouse.pop(); if(tmp.w-flow>0) {mouse.push(Node(tmp.w-flow,tmp.c));}
}
if(rst>0) {hole.push(Node(rst,-x+c));}
if(w-rst>0) {mouse.push(Node(w-rst,-x-c));}
}
int main()
{
scanf("%d%d",&n,&m); llong sum = 0ll;
for(int i=1; i<=n; i++) {scanf("%lld",&a[i].x);}
for(int i=1; i<=m; i++) {scanf("%lld%lld%lld",&b[i].x,&b[i].c,&b[i].w); sum += b[i].w;}
if(sum<n) {printf("-1"); return 0;}
int i = 1,j = 1;
while(i<=n||j<=m)
{
if(i<=n && (j>m||a[i].x<b[j].x)) {insertmouse(a[i].x); i++;}
else {inserthole(b[j].x,b[j].w,b[j].c); j++;}
}
printf("%lldn",ans);
return 0;
}