P2887

__stick · 2022-11-14 16:03:22 · 个人记录

题意

有 n 只奶牛，每只能接受值在 [l_i,r_i] 的防晒霜，m 支防晒霜，每支值为 x_i ，有 num_i 支，问最多有多少奶牛可以用上防晒霜。

思路

一个二分图模型，用网络流解决。

原点向奶牛连容量是 1 的边，每只奶牛向可以接受的防晒霜连边，每只防晒霜向汇点连容量为 num_i 的边，但是这样明显有 O(nm) 的边，空间上无法接受。这时候发现一只奶牛可以指向的防晒霜是连续的，所以考虑线段树优化建图。

具体说来，对防晒霜开线段树，线段树上从根节点向叶子节点连边，容量正无穷，每只牛向线段树查询出来的区间节点上连边，这样的边数就减少到了 O(n\log m) 级别，通过这道题就没有问题了。

线段树建图不清楚的可以去到 CF786B 学习一下。

code

const int MAXN=8000+10;
struct edge{int from,v;ll cap;}e[100004];

int cnt=1,n,m,s,t,head[MAXN];
inline void add(int u,int v,int cap)
{
    e[++cnt]=(edge){head[u],v,cap},head[u]=cnt;
    e[++cnt]=(edge){head[v],u,0},head[v]=cnt;
}
int d[MAXN],now[MAXN];
bool bfs()
{
    memset(d,0,sizeof(d));
    d[s]=1;queue<int>q;q.push(s);
    now[s]=head[s];
    while(!q.empty())
    {
        int u=q.front();q.pop();now[u]=head[u];
        for(int i=head[u];i;i=e[i].from)
        {
            int v=e[i].v;
            if(e[i].cap&&!d[v])
            {
                d[v]=d[u]+1;now[v]=head[v];
                q.push(v);
                if(v==t)return 1;
            }
        }
    }
    return 0;
}
ll dfs(int u,ll flow)
{
    if(u==t)return flow;
    ll res=0;
    for(int i=now[u];i&&flow;i=e[i].from)
    {
        int v=e[i].v;
        if(e[i].cap&&d[v]==d[u]+1)
        {
            ll k=dfs(v,min(flow,e[i].cap));
            if(!k){d[v]=0;continue;}
            e[i].cap-=k,e[i^1].cap+=k,flow-=k,res+=k;
        }
    }
    return res;
}
int lev[MAXN];
int tt;
struct xds
{
    xds* ls,*rs;
    int l,r,siz;
    int in;
    xds(int L,int R):l(L),r(R)
    {
        in=++tt;    
        if(L==R)
        {
            lev[L]=in;
            return;
        }   
        int mid=(L+R)>>1;
        ls=new xds(L,mid),rs=new xds(mid+1,R);
        add(in,ls->in,1<<30),add(in,rs->in,1<<30);
    }   
    void update(int ql,int qr,int k)
    {
        if(ql<=l&&r<=qr)return add(k,in,1<<30);
        int mid=(l+r)>>1;
        if(ql<=mid) ls->update(ql,qr,k);
        if(qr> mid) rs->update(ql,qr,k);
    };
};
int l[MAXN],r[MAXN];
pii p[MAXN];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    xds a(1,m);
    s=0,t=tt+n+1;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        add(s,tt+i,1);
    }
    for(int i=1;i<=m;i++)
    {
        int x,k;
        cin>>p[i].first>>p[i].second;
    }
    sort(p+1,p+m+1);
    for(int i=1;i<=n;i++)
    {
        int x=lower_bound(p+1,p+m+1,(pii){l[i],0})-p;
        int y=upper_bound(p+1,p+m+1,(pii){r[i],1e9})-p-1;//二分出来每只奶牛可以使用防晒霜的区间
        if(x<=y) a.update(x,y,tt+i);//不能调用空区间
    }
    for(int i=1;i<=m;i++)add(lev[i],t,p[i].second);//lev 表示 i 防晒霜在线段树上的节点编号
    ll ans=0;
    while(bfs())ans+=dfs(s,1<<30);
    cout<<ans;
    return 0;
}