题解：P15246 [WC2026] 猫和老鼠

· · 题解

更好的阅读体验

qoj 7，非常困难！

首先我们考虑以位置为 x 轴，时间为 y 轴建立一个二维平面。由于每个 bot 的运行速度都是 1 单位每秒，因此可以看作是若干条斜率为 \pm 1 的直线。由于老鼠的速度 \le 1 单位每秒，因此老鼠只能往右上方 45 \degree 和左上方 45 \degree 之间的方向移动，如图中红色区域。那么问题就转化为，老鼠从 x 轴上任意一点出发，能否阻止老鼠通过往指定方向（如上所述）移动，且横坐标始终位于 [0, m] 以内，最多碰到 k 次黑色斜线，到达纵坐标 + \infty 得区域。如果可以，求选择得黑色斜线得代价之和得最小值。

那么我们考虑两条线段要以怎样放置才能阻止老鼠通过这两条线。为了方便，我们现在将这个平面旋转 45 \degree 观察。则原来得 y 轴和直线 x = m 可以变成现在得坐标系下得直线 y = x 和 y = x + 2m；斜线变成了若干条和 x 轴或 y 轴平行得线段；老鼠的运行方向变成了只能向右上方行走。

现在考虑两条线段如何排布可以使老鼠无法通过。

我们先考虑 k = 1 的情况。容易发现，要求解的“使老鼠无法从 x = 0 处走到 x = + \infty 处的最小代价”相当于求解一个图上的最小割，而在这个图上，边代表一个 bot，点代表平面上的一块区域。这种建模非常抽象，因此我们考虑取对偶图。那么在对偶图上问题较为简单。对偶图的形态是这样的：

最大流（最小割）等价于对偶图上的最短路。注意这里是点权最短路。所以 k = 1 的情况下，我们对这个图求解 S \to T 的点权最短路即可。

接下来考虑 k > 1，问题就变成求 S 到 T 的 k 条点不交的路径，求最小的路径点权和。首先点权很难处理，考虑转化为边权，也就是将每个线段拆成两个点，分别称为入点和出点，入点向出点连有向边，边权为这条线段的代价。这里直接取两个路径的端点即可（这里约定对于和 y 轴平行的路径，连边的方向是上 \to 下，和 x 轴平行的路径，连边的方向是左 \to 右）。由于求得是 k 条不相交路径，不难想到使用有流量限制 k 的最小费用最大流。接下来需要考虑的是要如何在不同线段的出点和入点之间连边，满足上面所述的连边性质。

首先和 S 或 T 相连的边，直接枚举线段连接即可。

对于线段中间的边，我们考虑一个很高妙的建边方式：对于一个出点，将这个出点向该点左上方（包括正左，正上）的所有入点连边。

有何道理？如上图，绿色是按照上述规则新加入的边，容易验证，三种线段之间的连边方式，都可以使用上述的连边规则统一实现！

但是现在仍然无法通过，因为我们的总边数是 O(n^2) 的。但是连边的方式很像二位偏序，因此我们可以考虑 cdq 分治优化建边。

具体地，现在我们将所有出点和入点放在一起按照 x 坐标排序，假设现在要处理 [l, r] 区间内点之间的连边，则取区间中点 mid，我们只考虑 [mid+1, r] \to [l, mid] 的边。

那么我们把 [l, mid] 所有点的 y 坐标离散化，然后每个 [r, mid] 的点会连向左侧的点按照 y 坐标排序后的点的一个后缀。考虑对左侧的点使用后缀和优化建边，如图所示。假设左侧的点数为 c，则我们新建 c 个点 suf_1 \sim suf_c，其中 suf_c 连向排序后第 c 个点，suf_k (k < c) 连向排序后第 k 个点，还有 suf_{k+1}。这样就可以用 O(c) 条边得到每个后缀的连边！

那么现在最小费用最大流的点数和边数都是 O(n \log n)，使用原始对偶算法求解 MCMF，瓶颈就在于一开始求得一次 SPFA。但是我们发现，由于所有线段的价值为正，因此不需要额外跑一次 SPFA 初始化势能。由于有流量限制 k，因此最多增广 k 轮，而每一次增广的瓶颈在于 dijkstra。因此总复杂度为 O(kn \log^2 n)，可以通过。

#include<bits/stdc++.h>
//#include "game.h"
#define endl '\n'
#define N 1000006
#define M 6000006
using namespace std;
using i64=long long;
struct MCMF_Graph {
  struct Node {
    int u; i64 d;
    friend bool operator >(Node x,Node y) {return x.d>y.d;}
  };
  i64 dis[N],h[N];
  int tot,ecnt,head[N],s,t,vis[N];
  struct Edge {int to,next; i64 w,c;} E[M],fr[M];
  void addedge(int u,int v,i64 w,i64 c) {E[ecnt]={v,head[u],w,c},head[u]=ecnt++;}
  void addflow(int u,int v,i64 w,i64 c) {addedge(u,v,w,c),addedge(v,u,0,-c);}
  void init(int Tot,int S,int T)
  {
    for(int i=1;i<=tot;i++)dis[i]=h[i]=head[i]=vis[i]=0;
    for(int i=1;i<=ecnt;i++)E[i]=fr[i]={0,0,0,0};
    tot=Tot,s=S,t=T,ecnt=2;
  }
  int dijkstra()
  {
    priority_queue<Node,vector<Node>,greater<Node> > q;
    for(int i=0;i<=tot;i++)vis[i]=0,dis[i]=2e15;
    q.push({s,0}),dis[s]=0;
    while(q.size())
    {
      auto [u,d]=q.top(); q.pop();
      if(vis[u])continue;
      vis[u]=1;
      for(int i=head[u];i;i=E[i].next)
      {
        int v=E[i].to; i64 w=h[u]-h[v]+E[i].c;
        if(E[i].w&&dis[v]>dis[u]+w)
        {
          dis[v]=dis[u]+w,fr[v].next=i,fr[v].to=u;
          if(!vis[v])q.push({v,dis[v]});
        }
      }
    }
    return dis[t]<2e15;
  }
  pair<i64,i64> get_flow()
  {
    i64 maxflow=0,mincost=0;
    while(dijkstra())
    {
      i64 fl=1e18;
      for(int i=1;i<=tot;i++)h[i]+=dis[i];
      for(int i=t;i^s;i=fr[i].to)fl=min(fl,E[fr[i].next].w);
      for(int i=t;i^s;i=fr[i].to)
        E[fr[i].next].w-=fl,E[fr[i].next^1].w+=fl;
      maxflow+=fl,mincost+=fl*h[t];
    }
    return {maxflow,mincost};
  }
} G;
int tot,bn,suf_id[N];
vector<int> vec[N];
i64 b[N];
struct Node {i64 x,y; int id;} p[N];
void init(int c,int y) {}
void cdq(int l,int r)
{
  if(l==r)return;
  int mid=l+r>>1; cdq(l,mid),cdq(mid+1,r),bn=0;
  for(int i=l;i<=mid;i++)b[++bn]=p[i].y;
  sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
  for(int i=1;i<=bn;i++)vec[i].clear();
  for(int i=l,t;i<=mid;i++)if(p[i].id&1)
    t=lower_bound(b+1,b+1+bn,p[i].y)-b,vec[t].push_back(p[i].id);
  for(int i=bn;i;i--)
  {
    suf_id[i]=++tot;
    if(i!=bn)G.addflow(suf_id[i],suf_id[i+1],2e10,0);
    for(int j:vec[i])G.addflow(suf_id[i],j,2e10,0);
  }
  for(int i=mid+1,t;i<=r;i++)if(!(p[i].id&1)&&p[i].y<=b[bn])
    t=lower_bound(b+1,b+1+bn,p[i].y)-b,G.addflow(p[i].id,suf_id[t],2e10,0);
}
i64 game(int n,int m,int k,vector<int> a,vector<int> b,vector<int> t,vector<int> w)
{
  int S=n*2+1,fake_S=n*2+2,T=n*2+3;
  G.init(0,S,T),tot=n*2+3;
  G.addflow(S,fake_S,k,0);
  for(int i=0;i<n;i++)
  {
    i64 st_x=t[i]-a[i],st_y=t[i]+a[i];
    i64 ed_x=((i64)abs(a[i]-b[i]))+t[i]-b[i],ed_y=((i64)abs(a[i]-b[i]))+t[i]+b[i];
    // 奇数: in; 偶数: out
    if(st_x==ed_x)
    {
      if(st_y<ed_y)swap(st_x,ed_x),swap(st_y,ed_y);
      p[i*2+1]={st_x,st_y,i*2+1};
      p[i*2+2]={ed_x,ed_y,i*2+2};
    } else {
      if(st_x>ed_x)swap(st_x,ed_x),swap(st_y,ed_y);
      p[i*2+1]={st_x,st_y,i*2+1};
      p[i*2+2]={ed_x,ed_y,i*2+2};
    }
    if(st_y==st_x+2*m)G.addflow(fake_S,i*2+1,1,0);
    if(ed_y==ed_x)G.addflow(i*2+2,T,1,0);
    G.addflow(i*2+1,i*2+2,1,w[i]);
  }
  sort(p+1,p+1+n*2,[](Node x,Node y) {
    if(x.x!=y.x)return x.x<y.x;
    if(x.y!=y.y)return x.y>y.y;
    int typ_x=x.id&1,typ_y=y.id&1;
    return typ_x>typ_y;
  }),cdq(1,n*2),G.tot=tot;
  auto [maxflow,mincost]=G.get_flow();
  if(maxflow<k)return -1;
  return mincost;
}