CF536D Tavas in Kansas

(Updated: )
oi
,

题目链接：CF536D

  • 给定一张 $n$ 个点 $m$ 条边的可能有自环和重边的无向连通图，每条边都有一个非负边权。
  • 小 X 和小 Y 在这张图上玩一个游戏，在游戏中，第 $i$ 个城市有一个权值 $p_i$。
  • 一开始，小 X 在城市 $s$ 中，小 Y 在城市 $t$ 中，两人各有一个得分，初始为 $0$，小 X 为先手，然后轮流进行操作。
  • 当轮到某一个人时，他必须选择一个非负整数 $x$，以选定所有与他所在的城市的最短距离不超过 $x$ 的还未被选定过的城市，他的得分将会加上这些城市的权值。
  • 另外，每个人每次必须能够至少选定一个城市。
  • 当没有人可以选择时，游戏结束，得分高者获胜。
  • 现在请你计算出，在两人都使用最佳策略的情况下，谁会获胜（或者判断为平局）。
  • $n \le 2 \times 10^3$，$m \le 10^5$，$p_i \le 10^9$。

Tutorial

首先从 $s,t$ 分别跑一次最短路，容易发现答案仅与其相对大小有关，因此先离散化。

容易将其抽象成一个表格，其中第 $i$ 号点位于 $(d_{s,i},d_{t,i})$，权值为 $p_i$，两人分别从 上/左 取若干 行/列。

注意到 $n\leq 2\times 10^3$，考虑 dp，设 $f_{k,i,j}$ 表示在各自最优策略下当前小 X/小 Y 先手，剩余的点为 $(i,j)$ 及其右下角范围，小 X 的权值与小 Y 的权值的差。

发现其实没必要枚举每个人取到哪一行/列进行转移，只需要一行行一列列转移时注意是否要交给对方即可。
$$
\begin{align}
&f_{0,i,j}\leftarrow \max { f_{0,i+1,j} , f_{1,i+1,j}}+S(i,j,i,c_1) \quad [\exists p\in [i,j,i,c_1]]\\
&f_{1,i,j}\leftarrow \min { f_{0,i,j+1} , f_{1,i,j+1}}-S_{i,j,c_0,j} \quad[\exists p\in [i,j,c_0,j]]
\end{align}
$$
$O(N^2)$。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e3+10,M=1e5+10;
int n,m,s[2],a[N],vis[N],fir[N],nxt[M<<1],son[M<<1],w[M<<1],tot,cnt,c[2],sz[N][N];
LL sum[N][N],b[N],dp[2][N][N],F[2][N];
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z;}
#define to son[i]
queue<int> q;
I void Spfa(){
    RI u,i,j;for(memset(vis,0,sizeof(vis)),memset(F,63,sizeof(F)),j=0;j<2;j++){
        W(!q.empty()) q.pop();F[j][s[j]]=0,q.push(s[j]);W(!q.empty())
        for(vis[u=q.front()]=0,q.pop(),i=fir[u];i;i=nxt[i]) F[j][to]>F[j][u]+w[i]&&(F[j][to]=F[j][u]+w[i],!vis[to]&&(q.push(to),vis[to]=1));
    }
}
I int Sz(CI i1,CI j1,CI i2,CI j2){return sz[i2][j2]-sz[i1-1][j2]-sz[i2][j1-1]+sz[i1-1][j1-1];}
I LL Sum(CI i1,CI j1,CI i2,CI j2){return sum[i2][j2]-sum[i1-1][j2]-sum[i2][j1-1]+sum[i1-1][j1-1];}
int main(){
    RI i,j,k,x,y,z;for(read(n,m,s[0],s[1]),i=1;i<=n;i++) read(a[i]);
    for(i=1;i<=m;i++) read(x,y,z),Add(x,y,z),Add(y,x,z);
    for(Spfa(),k=0;k<2;k++){
        for(cnt=0,i=1;i<=n;i++) b[++cnt]=F[k][i];
        for(sort(b+1,b+cnt+1),c[k]=cnt=unique(b+1,b+cnt+1)-b-1,i=1;i<=n;i++) F[k][i]=lower_bound(b+1,b+cnt+1,F[k][i])-b;
    }
    for(i=1;i<=n;i++) sum[F[0][i]][F[1][i]]+=a[i],sz[F[0][i]][F[1][i]]++;
    for(i=1;i<=c[0];i++) for(j=1;j<=c[1];j++) sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1],sz[i][j]+=sz[i-1][j]+sz[i][j-1]-sz[i-1][j-1];
    for(i=c[0];i;i--) for(j=c[1];j;j--){
        if(Sz(i,j,i,c[1])) dp[0][i][j]=max(dp[0][i+1][j],dp[1][i+1][j])+Sum(i,j,i,c[1]);
        else dp[0][i][j]=dp[0][i+1][j];
        if(Sz(i,j,c[0],j)) dp[1][i][j]=min(dp[0][i][j+1],dp[1][i][j+1])-Sum(i,j,c[0],j);
        else dp[1][i][j]=dp[1][i][j+1];
    }
    return puts(dp[0][1][1]>0?"Break a heart":dp[0][1][1]<0?"Cry":"Flowers"),0;
}