题解：P10433 [JOIST 2024] 棋盘游戏 / Board Game
Aegleseeker_
·
·
题解
这应该是除了 exihibition 外我今年做过的最牛逼的题了吧。
下面称 s_i=1 的点为黑点，s_i=0 的点为白点。
部分分：没有黑点
直接跑最短路。
部分分：恰有一个黑点
分讨一下是 X_1 直接走到 T，还是途中走到黑点耗一个回合。前者是简单的，对于后者我们需要考虑 X_{[2,k]} 的最小消耗代价，使得这一回合能尽快结束并让决策者重新回到 X_1。预处理出以黑点 u 为起点的最短路，则 X_{[2,k]} 的总代价为 \sum\limits_{i=2}^kdis(X_i,u)，也就是每个人走到最近的黑点停下。
部分分：>1 个黑点，n,m,k\le 3000
上一档部分分启示我们当 X_1 途中经过黑点时，考虑如何计算 X_{[2,k]} 快速 pass 掉这一回合的最小代价。由于一个点上可以有多个人，不难发现每个 X_i 的代价都是独立的。显然每个 X_i 的策略无非两种：
- 走到最近的黑点停下，此后每次他从这个黑点往某个白点邻居蠕动一下，再蠕动回来。除第一轮外单轮 pass 的代价为 2。
- 前几轮经过一些黑点，最终在某个满足其邻域也有黑点的黑点停下。此后每次他从这个黑点往邻域中的黑点蠕动一下并停下，再下一轮就蠕动回来并停下。除了前几轮后单轮 pass 的代价为 1。
如果把 X_i 的消耗代价随轮数的函数画出来，那第一种策略对应的就是一条 k=2 的直线，第二种策略对应的就是一段 k\ge 2 的直线拼上一段 k=1 的直线，最终每个位置取个 \min 就可以得到这个函数。
那么这个函数肯定是前面一段 k=2 的直线拼上后面一段 k=1 的直线。k=2 的直线的截距容易求出，按照上一档部分分的做法跑最短路。比较难处理的是 k=1，注意到我们只关心截距，因此不妨直接将边权设为 1、黑点点权设为 -1，则跑出来的最短路就是长度减轮数的最小值，也就是截距的最小值。
求出了 k=1,2 的直线，解个方程找到两条直线的交点即可，那么我们就可以描述 X_i 消耗代价随轮数关系的这个函数了。写个差分把每个人的函数加起来就可以得到每一轮 X_{[2,k]} pass 掉一整轮的最小代价。
令 g_i 代表第 i 轮 X_{[2,k]} 总共消耗的最小代价，f_{i,T} 代表钦定经过恰 i 轮，X_1 走到 T 的最小代价。则 T 的答案可以表示为：\min\limits_{i=0}^nf_{i,T}+g_i。
### 部分分：$k$ 充分小
这档部分分该如何入手呢？
注意到 $g_i$ 是由 $O(k)$ 个只有 $O(1)$ 个拐点的上凸函数相加出来的，因此最终 $g_i$ 也是上凸的，且按斜率分段只会分出 $O(k)$ 段，对于其中的每一段，$g_i$ 都可以表示成 $ki+b$ 的形式。
考虑将这个代价拆到最短路的计算过程中，我们将边权设为 $1$，黑点点权设为 $k$，再跑最短路。则 $X_1$ 到 $T$ 的此时的最短路中代价就已经包含了 $g_i-b$ 的部分，最后再加上 $b$ 即可。
但很容易发现一个问题，我们是否需要保证最短路中经过黑点的次数在凸壳上这段斜率对应的区间内？注意到我们还有个凸性没有用到，显然如果你次数没在对应区间内，那由于点权是 $k$，所以结果算出来不如直接取那个次数对应段的结果。
因此只需跑 $O(k)$ 次最短路，复杂度 $O(kn\log n)$。注意到这个最短路比较特殊，权值只有 $1,k$ 两种，所以也可以写个 01 bfs 做到 $O(nk)$。
**警示后人：你需要注意这个凸壳在 $0$ 处是不满足凸性的！因此如果你跑最短路的途中一个黑点都没经过，那就有可能取到比答案更优的错解！因此你需要对 $dis$ 数组开一维 $0/1$ 代表目前是否经过黑点。**
### 思考：$k$ 充分大
注意到当 $X_1$ 抉择去走的轮数加一时，其余 $k-1$ 个点每个点都得耗费非 $0$ 的代价，因此不难发现轮数充分大是不优的，因为如果抉择的轮数比最小轮数多了 $O(\frac{n}{k})$，那 $X_{[2,k]}$ 部分的代价就增加了 $\ge n$，而 $X_1$ 的代价显然不能节约出来这么多，所以爆了。
对于每个 $T$，预处理出 $X_1$ 到 $T$ 经过的最小轮数 $x$，则显然答案取到的轮数在 $[x,x+O(\frac{n}{k})]$ 这个区间里。这个时候我们还是跑分层图 bfs，但只保留层数在对应区间里的点，这样复杂度就是 $O(\frac{n^2}{k})$ 的了。
### 正解
那么对 $k$ 根号分治即可。
复杂度 $O(n\sqrt {n\log n})$ 或 $O(n\sqrt n)$。
由于本题非常难写，下面同时给出代码和 gen（by AI）。如果你 WA 了，可以在题解区和你喜欢的题解对拍一下。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50005;
const int B=230;
int n,m,k;
string s;
int posx[N],vis[N],vis0[N],vis1[N][2],val[N];
int disx[N],dis[N],dis0[N],dis1[N][2],sx[N],ans[N],ans0[N];
int L[N],R[N],dis2[N][B+5],vis2[N][B+5];
vector<int> g[N];
struct node{
int x,key,type;
bool operator <(const node &b)const{
return key>b.key;
}
};
void dijkstra1(){
priority_queue<node> q;
for(int i=1;i<=n;i++) vis1[i][0]=vis1[i][1]=0,dis1[i][0]=dis1[i][1]=1e18;
dis1[posx[1]][0]=0;
q.push(node{posx[1],dis1[posx[1]][0],0});
while(!q.empty()){
int u=q.top().x,t=q.top().type;
q.pop();
if(vis1[u][t]) continue;
vis1[u][t]=1;
for(auto v:g[u]){
int tv=(t||(s[u]=='1'&&u!=posx[1]));
if(dis1[v][tv]>dis1[u][t]+1+val[v]){
dis1[v][tv]=dis1[u][t]+1+val[v];
q.push(node{v,dis1[v][tv],tv});
}
}
}
}
void dijkstra2(){
priority_queue<node> q;
for(int i=1;i<=n;i++) vis[i]=0,dis[i]=1e18;
dis[posx[1]]=0;
q.push(node{posx[1],dis[posx[1]]});
while(!q.empty()){
int u=q.top().x;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto v:g[u]){
if(dis[v]>dis[u]+(s[v]=='1')){
dis[v]=dis[u]+(s[v]=='1');
q.push(node{v,dis[v]});
}
}
}
}
void dijkstra0(){
priority_queue<node> q;
for(int i=1;i<=n;i++) vis[i]=0,dis0[i]=1e18;
dis0[posx[1]]=0;
q.push(node{posx[1],dis0[posx[1]]});
while(!q.empty()){
int u=q.top().x;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto v:g[u]){
if(dis0[v]>dis0[u]+1){
dis0[v]=dis0[u]+1;
if(s[v]!='1') q.push(node{v,dis0[v]});
}
}
}
}
void initdij(){
priority_queue<node> q;
for(int i=1;i<=n;i++){
vis[i]=0;
if(s[i]=='1'){
bool flag=0;
for(auto j:g[i]) if(s[j]=='1') vis0[i]=1,flag=1;
if(flag) dis[i]=-1,q.push(node{i,-1});
else dis[i]=1e18;
}else dis[i]=1e18;
}
while(!q.empty()){
int u=q.top().x;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto v:g[u]){
if(dis[v]>dis[u]+1+(s[v]=='1'?-1:0)){
dis[v]=dis[u]+1+(s[v]=='1'?-1:0);
q.push(node{v,dis[v]});
}
}
}
}
void init(){
queue<int> q;
for(int i=1;i<=n;i++){
if(s[i]=='1'){
q.push(i);
vis[i]=1;
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:g[u]){
if(vis[v]) continue;
disx[v]=disx[u]+1,vis[v]=1,q.push(v);
}
}
initdij();
for(int i=1;i<=n;i++){
if(!disx[i]) disx[i]=2;
if(vis0[i]) dis[i]=0;
else if(s[i]=='1') dis[i]++;
}
for(int i=2;i<=k;i++){
//2*(t-1)+disx[posx[i]]
//t+dis[posx[i]]
//>=t,choose k=1
sx[i]=max(1ll,dis[posx[i]]-disx[posx[i]]+2);
}
dijkstra0();
for(int i=1;i<=n;i++) ans[i]=1e18,ans0[i]=dis0[i];
}
int valk[N],valb[N];
void subtask1(){
int lst=1;
for(int i=2;i<=n;i++){
if(valk[i]!=valk[lst]){
for(int j=1;j<=n;j++){
if(s[j]=='1') val[j]=valk[lst];
else val[j]=0;
}
dijkstra1();
for(int j=1;j<=n;j++){
int res=dis1[j][1]+valb[lst];
if(s[j]=='1') res-=valk[lst];
ans[j]=min(ans[j],res);
}
lst=i;
}
}
for(int j=1;j<=n;j++){
if(s[j]=='1') val[j]=valk[lst];
else val[j]=0;
}
dijkstra1();
for(int j=1;j<=n;j++){
int res=dis1[j][1]+valb[lst];
if(s[j]=='1') res-=valk[lst];
ans[j]=min(ans[j],res);
}
}
void subtask2(){
for(int i=1;i<=n;i++) val[i]=valk[i]*i+valb[i];
dijkstra2();
for(int i=1;i<=n;i++) if(s[i]=='1'&&i!=posx[1]) dis[i]--;
queue<pair<int,int> > q;
for(int i=1;i<=n;i++){
for(int j=0;j<=min(B,n/k);j++){
dis2[i][j]=1e18,vis2[i][j]=0;
}
}
q.push({posx[1],0}),dis2[posx[1]][0]=0;
while(!q.empty()){
int u=q.front().first,i=q.front().second;
q.pop();
if(vis2[u][i]) continue;
vis2[u][i]=1;
for(auto v:g[u]){
int j=i+dis[u]-dis[v]+(s[u]=='1'&&u!=posx[1]);
if(j<0||j>min(B,n/k)||dis2[v][j]<=dis2[u][i]) continue;
dis2[v][j]=dis2[u][i]+1;
q.push({v,j});
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=min(B,n/k);j++){
ans[i]=min(ans[i],dis2[i][j]+val[j+dis[i]]);
}
}
}
signed main(){
//freopen("test.in","r",stdin);
//freopen("my.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v),g[v].push_back(u);
}
cin>>s,s=" "+s;
for(int i=1;i<=k;i++) cin>>posx[i];
bool flag=0;
for(int i=1;i<=n;i++) flag|=(s[i]=='1');
if(!flag){
queue<int> q;
q.push(posx[1]),vis[posx[1]]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:g[u]){
if(vis[v]) continue;
dis[v]=dis[u]+1,vis[v]=1,q.push(v);
}
}
for(int i=1;i<=n;i++) cout<<dis[i]<<'\n';
return 0;
}
init();
for(int i=2;i<=k;i++){
valk[1]+=2,valb[1]+=disx[posx[i]]-2;
if(sx[i]<=n){
valk[sx[i]]--;
valb[sx[i]]+=dis[posx[i]]-disx[posx[i]]+2;
}
}
for(int i=1;i<=n;i++) valk[i]+=valk[i-1],valb[i]+=valb[i-1];
if(k<=B) subtask1();
else subtask2();
for(int i=1;i<=n;i++) cout<<min(ans0[i],ans[i])<<'\n';
return 0;
}
```
gen：
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("test.in","w",stdout);
mt19937 rng(time(0));
int n=rng()%20+5,m=rng()%(n*(n-1)/2-(n-1))+n-1,k=rng()%(n-1)+2;
vector<int> perm(n);
for (int i = 0; i < n; ++i) perm[i] = i + 1;
shuffle(perm.begin(), perm.end(), rng);
set<long long> edge_set;
auto encode = [&](int u, int v) {
if (u > v) swap(u, v);
return 1LL * u * (n + 1) + v;
};
vector<pair<int, int>> edges;
for (int i = 1; i < n; ++i) {
int u = perm[i];
int v = perm[uniform_int_distribution<int>(0, i - 1)(rng)];
edges.emplace_back(u, v);
edge_set.insert(encode(u, v));
}
uniform_int_distribution<int> vertex_dist(1, n);
while ((int)edges.size() < m) {
int u = vertex_dist(rng);
int v = vertex_dist(rng);
if (u == v) continue;
long long code = encode(u, v);
if (edge_set.find(code) == edge_set.end()) {
edge_set.insert(code);
edges.emplace_back(u, v);
}
}
cout<<n<<' '<<m<<' '<<k<<'\n';
for (auto &[u, v] : edges) {
cout << u << " " << v << "\n";
}
for(int i=1;i<=n;i++) cout<<rng()%2;
cout<<'\n';
for(int i=1;i<=k;i++) cout<<rng()%n+1<<' ';
return 0;
}
```