[CF536D]Tavas in Kansas
题目大意：
一张\(n(n\le2000)\)个点，\(m(m\le10^5)\)条边的无向带权连通图（权值可以为负）。A、B两人分别在\(s,t\)点进行博弈。A先手，每次每人可以选择一个数\(x\)，并取走到当前位置距离\(\le x\)的点，自己的得分加上这些点的权值之和。每次至少取走一个点，去过的点不能再取。取完所有的点后，得分最高者胜。若每个人都按照最后策略进行游戏，求最后的赢家。
思路：
首先求\(s,t\)的单元最短路。对于每个点，我们可以知道它是离\(s\)第\(x\)远的点，离\(t\)第\(y\)远的点。我们将它当作二维平面上的点\((x,y)\)，那么游戏就相当于A每次取一行，B每次取一列。
用\(f[i][j][0/1]\)表示取前\(i\)行，前\(j\)列，最后一个人是A还是B，此时\(A-B\)在最优策略下的得分。
转移方程显然，反着DP可以少一些特判。
源代码：
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<functional>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
typedef long long int64;
const int N=2001;
int n,w[N],s[2],tot[2],cnt[2][N][N];
struct Edge {
int to,w;
};
std::vector<Edge> e[N];
inline void add_edge(const int &u,const int &v,const int &w) {
e[u].push_back((Edge){v,w});
e[v].push_back((Edge){u,w});
}
int64 dis[2][N],hash[N],f[N][N][2],sum[2][N][N];
struct Vertex {
int id;
int64 d;
bool operator > (const Vertex &rhs) const {
return d>rhs.d;
}
};
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q;
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[N];
inline void dijkstra(const int &s,int64 dis[]) {
for(register int i=1;i<=n;i++) {
p[i]=q.push((Vertex){i,dis[i]=i==s?0:LLONG_MAX});
}
while(!q.empty()) {
const int x=q.top().id;
q.pop();
for(auto &j:e[x]) {
const int &y=j.to,&w=j.w;
if(dis[x]+w<dis[y]) {
q.modify(p[y],(Vertex){y,dis[y]=dis[x]+w});
}
}
}
}
int main() {
n=getint();
const int m=getint();
s[0]=getint(),s[1]=getint();
for(register int i=1;i<=n;i++) {
w[i]=getint();
}
for(register int i=0;i<m;i++) {
const int u=getint(),v=getint();
add_edge(u,v,getint());
}
for(register int i=0;i<2;i++) {
dijkstra(s[i],dis[i]);
std::copy(&dis[i][1],&dis[i][n]+1,&hash[1]);
std::sort(&hash[1],&hash[n]+1);
tot[i]=std::unique(&hash[1],&hash[n]+1)-&hash[1];
for(register int j=1;j<=n;j++) {
dis[i][j]=std::lower_bound(&hash[1],&hash[tot[i]]+1,dis[i][j])-hash;
}
}
for(register int i=1;i<=n;i++) {
sum[0][dis[0][i]][dis[1][i]]+=w[i];
sum[1][dis[0][i]][dis[1][i]]+=w[i];
cnt[0][dis[0][i]][dis[1][i]]++;
cnt[1][dis[0][i]][dis[1][i]]++;
}
for(register int i=1;i<=tot[0];i++) {
for(register int j=1;j<=tot[1];j++) {
sum[0][i][j]+=sum[0][i][j-1];
sum[1][i][j]+=sum[1][i-1][j];
cnt[0][i][j]+=cnt[0][i][j-1];
cnt[1][i][j]+=cnt[1][i-1][j];
}
}
for(register int i=tot[0];i>=0;i--) {
for(register int j=tot[1];j>=0;j--) {
if(i==tot[0]&&j==tot[1]) continue;
if(i!=tot[0]) {
const int64 s=sum[0][i+1][tot[1]]-sum[0][i+1][j];
if(cnt[0][i+1][tot[1]]-cnt[0][i+1][j]) {
f[i][j][0]=std::max(f[i+1][j][0],f[i+1][j][1])+s;
} else {
f[i][j][0]=f[i+1][j][0];
}
}
if(j!=tot[1]) {
const int64 s=sum[1][tot[0]][j+1]-sum[1][i][j+1];
if(cnt[1][tot[0]][j+1]-cnt[1][i][j+1]) {
f[i][j][1]=std::min(f[i][j+1][0],f[i][j+1][1])-s;
} else {
f[i][j][1]=f[i][j+1][1];
}
}
}
}
const int64 ans=f[0][0][0];
if(ans>0) puts("Break a heart");
if(ans==0) puts("Flowers");
if(ans<0) puts("Cry");
return 0;
}