題目鏈接

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

題解

模擬費(fèi)用流，一個(gè)非常神奇的東西。
本題即為WC2019 laofu的講課中的Problem 8，經(jīng)典的老鼠進(jìn)洞模型，洞有容量和額外權(quán)值。
這道題的Subtask 4,5,6,7分別對(duì)應(yīng)著老鼠進(jìn)洞的最基礎(chǔ)模型、洞有額外權(quán)值、洞有容量、洞有容量和額外權(quán)值四個(gè)變形。
讓我們從最簡單的開始各個(gè)擊破。

Subtask 4

注: 本部分配合WC2019課件里的代碼圖理解效果更佳。
數(shù)軸上有\(n\)只老鼠(坐標(biāo)\(x_i\))和\(m\)個(gè)洞(坐標(biāo)\(y_i\))，每個(gè)老鼠必須進(jìn)一個(gè)洞，每個(gè)洞至多進(jìn)一只老鼠，最小化距離和。
假設(shè)洞\(i\)匹配了老鼠\(j\), 則若\(y_i<x_j\)代價(jià)為\(x_j+(-y_i)\), 否則為\((-x_j)+y_i\)，不妨拆成\(i,j\)兩部分分別計(jì)算。
使用可撤銷貪心的策略。
維護(hù)一個(gè)老鼠堆和一個(gè)洞堆，從左到右掃描。
若當(dāng)前掃到一只老鼠\(i\)，那么先隨便匹配一個(gè)目前空閑的洞（不妨假設(shè)負(fù)無窮遠(yuǎn)處有無窮多個(gè)洞），從洞堆中取出一個(gè)元素\(j\)匹配，其代價(jià)為\(x_i+j\)
考慮當(dāng)后面插入洞的時(shí)候允許老鼠反悔（像極了費(fèi)用流的反向邊）而匹配新的洞，那么如果一個(gè)老鼠反悔而匹配了右面的新洞\(k\), 那么代價(jià)的增量為\((y_k-x_i)-(x_i+j)=y_k+(-2x_i-j)\), 所以往老鼠堆中插入元素\(-2x_i-j\).
若當(dāng)前掃到一個(gè)洞\(j\)，考慮是否有老鼠要反悔，從老鼠堆中取出一個(gè)元素\(i\), 若反悔的代價(jià)\(y_j+i>0\)那么讓這個(gè)老鼠堆中的老鼠反悔，同時(shí)往洞堆中加入元素\(-2y_j-i\)，表示后面的老鼠再匹配這個(gè)洞的代價(jià)；否則只往洞堆中插入元素\(-y_j\).
時(shí)間復(fù)雜度\(O(n\log n)\).

Subtask 5

洞有額外權(quán)值\(w\)，怎么辦呢？
考慮這樣和原來有什么區(qū)別: 原來只有老鼠會(huì)反悔（因?yàn)椴粫?huì)有舍近求遠(yuǎn)故意匹配較遠(yuǎn)洞的情況），但是現(xiàn)在可能出現(xiàn)了！
解決辦法：讓洞和洞匹配，洞也可以反悔。
插入洞\(i\)時(shí)，除了往洞堆中插入元素之外，往老鼠堆也插入元素，表示該洞反悔的代價(jià)。插入的元素是\(-y_i-w_i\), 相當(dāng)于用新洞\(j\)替代該洞會(huì)少這么多的代價(jià)再加上\(y_j+w_j\).
坑：WC課件中那個(gè)“老鼠和洞同時(shí)反悔不優(yōu)”目前沒看明白。

Subtask 6

洞有容量。
有一個(gè)神仙做法，見WC課件或UOJ題解。
正常做法: 往堆里存一個(gè)pair, 記錄價(jià)值和剩余容量。
每次增廣會(huì)使一個(gè)往左走的老鼠改為往右走，因此復(fù)雜度正確。

Subtask 7

洞有容量，也有附加權(quán)值，顯然Subtask 6的做法時(shí)間復(fù)雜度錯(cuò)誤。
但是我們發(fā)現(xiàn)，如果兩個(gè)老鼠\(i,j\)分別匹配洞\(k\)且\(x_i<x_j<y_k\), 那么這兩種情況下往洞堆中丟的元素是一樣的，都是\(-y_k-w_k\).
所以我們可以“批量加入、批量增廣”，這樣復(fù)雜度就得到了保證。
其實(shí)這個(gè)東西就已經(jīng)非常像費(fèi)用流增廣的過程了。
費(fèi)用流的一條重要性質(zhì)是: 如果不是每次選全局最短路，而是按另一順序?qū)驮袋c(diǎn)相連的邊必須連的點(diǎn)進(jìn)行增廣，那么也是正確的。

建議結(jié)合代碼以獲取更好理解。

代碼

代碼寫出來發(fā)現(xiàn)和費(fèi)用流神相似！

#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("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的UOJ #455 [UER #8]雪灾与外卖 (贪心、模拟费用流)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。