P11509 [ROIR 2017 Day 1] 挖矿机器人

· · 题解

等了一周还没等到题解/qd。

做法来自官方题解。俄语翻译真的难以理解。

首先二分答案，判断前 k 个批次能否全部满足要求。

将问题转为二分图匹配，左部点为每个机器人，右部点为每个位置（每个格子对应着 q 个右部点），若机器人可以走到对应点则连边。

直接建出二分图显然会爆炸，考虑使用 hall 定理 进行判定。

根据 hall 定理，要对每一个子集进行判定，这样显然不可接受。考虑子集中存在移动能力为 d 的一个机器人，那么移动能力 \le d 的机器人都一定要被选进来，因为此时邻域大小 |N(S)| 不变，而 |S| 的大小增加，因此得到了一个更紧的限制。

于是将每个基地的机器人按照移动能力进行排序，枚举每个基地移动能力的最大值 c_i，统计每个基地移动能力 \le c_i 的机器人个数总和 s，同时统计每个基地所对应的矩形的并的面积 S，若 s\le S 则这个子集满足要求。

统计矩形面积并可以用容斥做到 O(2^s)。不完整批次的机器人个数可以用第 k 批的机器人数量减去 \max(s-S) 得到。

时间 O\big(\big(\dfrac{2t}{s}\big)^s\log n\big)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int w,h,s,q;
int ax[5],ay[5];
int n;
int b[103],d[103];
ll a[103];
//b:foundation
//a:number of bots
//d:distance
ll f[5];
int cnt[5],g[5];
struct node{
    ll x;int dis;
}p[5][103];
bool cmp(node x,node y){return x.dis<y.dis;}
struct rec{
    int ax,ay,bx,by;
}c[5],I;
rec merge(rec x,rec y)
{
    if(x.ax==-1||y.ax==-1)return I;
    if(x.ax==0)return y;
    if(y.ax==0)return x;
    rec c;
    c.ax=max(x.ax,y.ax);
    c.bx=min(x.bx,y.bx);
    c.ay=max(x.ay,y.ay);
    c.by=min(x.by,y.by);
    if(c.ax>c.bx||c.ay>c.by)c.ax=-1;
    return c;
}
ll sqm(rec x)
{
    if(x.ax<=0)return 0;
    return 1ll*(x.bx-x.ax+1)*(x.by-x.ay+1);
}
ll sq;
void calc(int x,int now,rec w)
{
    if(x>s)
    {
        if(now%2==0)sq-=sqm(w);
        else sq+=sqm(w);
        return;
    }
    calc(x+1,now,w);
    calc(x+1,now+1,merge(w,c[x]));
}
int flag;
ll res;
void dfs(int x)
{
    if(x>s)
    {
        for(int i=1;i<=s;i++)
        {
            if(g[i]==-1)c[i]=I;
            else
            {
                c[i].ax=max(1,ax[i]-g[i]);
                c[i].bx=min(w,ax[i]+g[i]);
                c[i].ay=max(1,ay[i]-g[i]);
                c[i].by=min(h,ay[i]+g[i]);
            }
        }
        sq=0;calc(1,0,(rec){0,0,0,0});
        ll ss=0;
        for(int i=1;i<=s;i++)ss+=f[i];
        if(sq*q<ss)flag=0,res=max(res,ss-sq*q);
        return;
    }
    f[x]=0;
    for(int i=0;i<=cnt[x];i++)
    {
        g[x]=p[x][i].dis;
        dfs(x+1);
        f[x]+=p[x][i+1].x;
    }
}
bool check(int x)
{
    flag=1;res=0;
    for(int i=1;i<=s;i++)cnt[i]=0,p[i][0].dis=-1;
    for(int i=1;i<=x;i++)
    {
        ++cnt[b[i]];
        p[b[i]][cnt[b[i]]]=(node){a[i],d[i]};
    }
    for(int i=1;i<=s;i++)sort(p[i]+1,p[i]+cnt[i]+1,cmp);
    dfs(1);
    return flag;
}
int main()
{
    scanf("%d %d %d %d",&w,&h,&s,&q);
    for(int i=1;i<=s;i++)scanf("%d %d",&ax[i],&ay[i]);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d %lld %d",&b[i],&a[i],&d[i]);
    I.ax=-1;int ans=0;
    int l=1,r=n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    check(ans+1);
    printf("%d %lld\n",ans,a[ans+1]-res);
    return 0;
}