模拟费用流

455. 【UER #8】雪灾与外卖

题意：

一条直线上有只老鼠，个洞。每只老鼠有一个坐标，每个洞也有一个坐标。

每个洞有一个容纳量，和一个权值。

第只老鼠和第个洞匹配，代价为：

问最小的代价。

题解:

模拟费用流，个人感觉就是个可反悔的堆。

有种情况:

具体见代码

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int inf=1e13; 
const int N=1e6+5;
int n,m,ans;
struct node{
    int pos,val,sum,opt;
}a[N];
struct Node{
    int val,sum;
};
bool operator < (Node a,Node b)
{
    return a.val>b.val;
}
priority_queue<Node>Mouse;
priority_queue<Node>Hole;
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
bool cmp(node a,node b)
{
    if(a.pos==b.pos)return a.opt>b.opt;
    return a.pos<b.pos;
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i].pos=read();
    int gs=n,sum=0;
    for(int i=1;i<=m;i++)
    {
        a[++gs].pos=read();
        a[gs].val=read();
        a[gs].sum=read();
        a[gs].opt=1;
        sum+=a[gs].sum;
    }
    if(sum<n){puts("-1");return 0;}
    gs++;
    a[gs].pos=-inf;
    a[gs].val=0;
    a[gs].sum=n;
    a[gs].opt=1;
    gs++;
    a[gs].pos=inf;
    a[gs].val=0;
    a[gs].sum=n;
    a[gs].opt=1;    
    sort(a+1,a+gs+1,cmp);
    for(int i=1;i<=gs;i++)
    {
        if(a[i].opt==1)
        {
            int t=a[i].sum;
            while(!Mouse.empty()&&t&&a[i].pos+a[i].val+Mouse.top().val<0)
            {
                Node u=Mouse.top();Mouse.pop();
                int d=min(t,u.sum);
                ans+=d*(a[i].pos+a[i].val+u.val);
                Hole.push((Node){-2*a[i].pos-u.val,d});
                //4.洞找了鼠，变成洞，可以使后面的鼠来换鼠(不换就是2) 
                t-=d;
                u.sum-=d;
                if(u.sum)Mouse.push(u);
            } 
            if(a[i].sum!=t)
            {
                Mouse.push((Node){-a[i].pos-a[i].val,a[i].sum-t});
                //5.洞找了鼠，变成鼠，可以使后面的洞来换洞
                //洞没有权值的情况下，匹配肯定没有交叉的情况
                //洞有权值，就会出现不要某个洞，而去选择后面的洞 
            }
            if(t)Hole.push((Node){-a[i].pos+a[i].val,t});
        }
        else{    
            Node u=Hole.top();Hole.pop();
            ans+=a[i].pos+u.val;
            Mouse.push((Node){-2*a[i].pos-u.val,1});
            //3.鼠找了洞，变成鼠，可以使后面的洞来换洞 (不换就是1)
            //为什么没有6.鼠找了洞，变成洞，可以可以使后面的鼠来换鼠
            //因为鼠是没有权值的，所以不会出现交叉的情况
            //即不会出现洞1-鼠2，洞2-鼠1，一定是洞1-鼠1，洞2-鼠2 
            u.sum--;
            if(u.sum)Hole.push(u);
        }
    }
    cout<<ans;
    return 0;
}
/*
5 5
10 3 1 9 1 
4 0 1
2 2 1
5 0 2
5 1 1
4 4 1

18
*/

注意：

由于老鼠没有权值，所以不需要。

同理，如果洞也没有权值，那么就不需要了。

Masha与老鼠

题意：

一条直线上有只老鼠，个洞。每只老鼠有一个坐标，每个洞也有一个坐标。

每个洞有一个容纳量。

第只老鼠和第个洞匹配，代价为：

问最小的代价。

题解

就是上一题，洞没有权值的情况。

由于洞没有权值，那么就不需要了。

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define next Nxt
#define last Lst
//#define gc getchar
#define int long long
const int N=3e6+5;
int n,m,ans;
struct node{
    int pos,sum,opt;
}a[N];
struct Node{
    int val,sum;
};
bool operator < (Node a,Node b)
{
    return a.val>b.val;
}
priority_queue<int,vector<int>,greater<int> >Mouse;
priority_queue<Node>Hole;
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
bool cmp(node a,node b)
{
    return a.pos<b.pos;
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i].pos=read();
    int gs=n,sum=0;
    for(int i=1;i<=m;i++)
    {
        gs++;
        a[gs].pos=read();a[gs].sum=read();a[gs].opt=1;
        sum+=a[gs].sum;
    }
    if(sum<n){puts("-1");return 0;}
    a[++gs]=(node){-200000000000,n,1};
    a[++gs]=(node){200000000000,n,1};
    sort(a+1,a+gs+1,cmp);
    for(int i=1;i<=gs;i++)
    {
        if(a[i].opt==1)
        {
            int t=a[i].sum;
            while(!Mouse.empty()&&t&&a[i].pos+Mouse.top()<0)
            {
                ans+=a[i].pos+Mouse.top();
                Hole.push((Node){-2*a[i].pos-Mouse.top(),1});
                Mouse.pop();
                t--;
            }
            if(t)Hole.push((Node){-a[i].pos,t});
        }
        else{
            Node u=Hole.top();Hole.pop();
            ans+=a[i].pos+u.val;
            Mouse.push(-2*a[i].pos-u.val);
            u.sum--;
            if(u.sum)Hole.push(u);
        }
    }
    cout<<ans;
}