资讯详情

更差的阅读体验

---

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\) 轴平行得线段；老鼠的运行方向变成了只能向右上方行走。

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

• 若两条线段相交，则显然老鼠无法通过两条线段得交点。
• 若两条线段都与 \(y\) 轴平行，且较左的线段的上端点 \(y\) 坐标 \(\ge\) 较右的线段的下端点 \(y\) 坐标，由于老鼠不能向下走，因此这种情况下，两条线段之间的空隙老鼠无法通过。
• 若两条线段都与 \(x\) 轴平行，且较下的线段的右端点 \(x\) 坐标 \(\ge\) 较上线段左端点的 \(x\) 坐标，由于老鼠不能往左走，因此这种情况下，两条线段之间的空隙老鼠无法通过。

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

• 若一条线段与 \(y = x + 2m\) 相交，则让源点 \(S\) 向这条线段连有向边。
• 若一条线段与 \(y = x\) 相交，则让这条线段向汇点 \(T\) 连有向边。
• 如果两条线段 \(i, j\) 满足 \(i, j\) 相交，则 \(i, j\) 互相连有向边。
• 若 \(i, j\) 都与 \(y\) 轴平行，且 \(i, j\) 这两条线段能够阻挡老鼠通过，则 \(i\) 向 \(j\) 连有向边，其中 \(i\) 的 \(x\) 坐标 \(< j\) 的 \(x\) 坐标。
• 若 \(i, j\) 都与 \(x\) 轴平行，且 \(i, j\) 这两条线段能够阻挡老鼠通过，则 \(i\) 向 \(j\) 连有向边，其中 \(i\) 的 \(y\) 坐标 \(< j\) 的 \(y\) 坐标。

最大流（最小割）等价于对偶图上的最短路。注意这里是点权最短路。所以 \(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; 偶数: outif(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;
}