CF536D Tavas in Kansas
题目链接：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，两人分别从 上/左 取若干 行/列。
注意到 nleq 2times 10^3，考虑 dp，设 f_{k,i,j} 表示在各自最优策略下当前小 X/小 Y 先手，剩余的点为 (i,j) 及其右下角范围，小 X 的权值与小 Y 的权值的差。
发现其实没必要枚举每个人取到哪一行/列进行转移，只需要一行行一列列转移时注意是否要交给对方即可。
Solution
代码语言：javascript复制#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 '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;
}
