P11268 MX-S5-T2 题解

· · 题解

建模

首先建出费用流模型。

答案就是最小费用最大流的费用。

模拟费用流

在这张图上模拟寻找增广路径的过程。我们管物品到 B 的边叫一类，到优惠券的边叫二类。增广路径有四种。

一、走一类边，费用为 b_i。

二、走二类边，费用为 a_i-v_j。

三、走二类边，再走二类反边，再走一类边，费用为 (a_i-v_j)-(a_k-v_j)+b_k=a_i-(a_k-b_k)。

四、走二类边，再走二类反边，再走另一条二类边。费用为 (a_i-v_j)-(a_k-v_j)+(a_k-v_l)=a_i-v_l。

优化增广过程

首先我们发现第四类增广是没用的。因为如果有第四类增广，则需要已经存在流 S\to j\to k \to T，结合物品使用优惠券的条件，有 a_j-v_k<a_i-v_k,a_j\ge w_l \Rightarrow a_i\ge w_l。i 与 l 之间有直接连边，与第二类增广等价。通俗易懂的来说，也就是两个物品，两个优惠券，如果两两可以匹配，那么交换他们的优惠券没有任何意义。

现在只需要考虑前三种了。但是好像还是不太好去维护我们每次最优的增广方案是什么。

注意到（注意力惊人）如果我们把物品按照 a 从小到大的顺序排序，每次寻找增广路钦定要走 S 到当前 a 最小的点（物品），答案是对的。证明如下：

首先一定会增广 n 次，每次新加的增广路径一定经过一个没选过的物品。

接下来考虑两个物品 i,j，不妨设 a_i<a_j。

对于第一类增广，由于 B\to T 这条边容量无限，所以怎么交换顺序都是一样的。

对于第二类增广，w>a_i 的优惠券，只有 j 能使用，故顺序不影响。w<a_i 的优惠券，由于优惠的价固定是 v，且 a_i<a_j，i 使用之费用更小，i 应当在 j 前面。

对于第三类增广费用为 a_i-(a_k-b_k)，其中 a_k-b_k 是与 i,j 无关的量，所以这种情况下 i 也应当在 j 前面。

综上，不管哪种增广方式，如果 a_i<a_j，把 i 放在 j 前面都是合理的。

于是我们可以将物品先排序，然后对于物品 i，三种方案是 b_i,a_i-\max v_j,a_i-\max a_k-b_k，这两个 max 用堆维护即可，由于每个元素只进出堆一次，所以复杂度 O(n\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+5;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
int n,m;
pii item[N],coupon[N];//first=a,w second=b,v;
priority_queue<ll> vw,ab;
int match[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>item[i].fi>>item[i].se;
    for(int i=1;i<=m;i++)cin>>coupon[i].fi>>coupon[i].se;
    sort(item+1,item+1+n);
    sort(coupon+1,coupon+1+m);
    int ptr=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        while(ptr<=m&&coupon[ptr].fi<=item[i].fi){
            vw.push(coupon[ptr].se);
            ptr++;
        }
        ll w1=item[i].se;
        ll w2=vw.empty()?1ll<<40:item[i].fi-vw.top();
        ll w3=ab.empty()?1ll<<40:item[i].fi-ab.top();
        ll mn=min({w1,w2,w3});
        if(mn==w1)ans+=w1;
        else if(mn==w2){
            ans+=w2;
            ab.push(item[i].fi-item[i].se);
            vw.pop();
        }
        else{
            ans+=w3;
            ab.pop();
            ab.push(item[i].fi-item[i].se);
        }
    }
    cout<<ans;
    return 0;
}