题目
题目链接：https://codeforces.com/problemset/problem/536/D
- 给定一张 (n) 个点 (m) 条边的可能有自环和重边的无向连通图，每条边都有一个非负边权。
- 小 X 和小 Y 在这张图上玩一个游戏，在游戏中，第 (i) 个城市有一个权值 (p_i)。
- 一开始，小 X 在城市 (s) 中，小 Y 在城市 (t) 中，两人各有一个得分，初始为 (0)，小 X 为先手，然后轮流进行操作。
- 当轮到某一个人时，他必须选择一个非负整数 (x)，以选定所有与他所在的城市的最短距离不超过 (x) 的还未被选定过的城市，他的得分将会加上这些城市的权值。
- 另外，每个人每次必须能够至少选定一个城市。
- 当没有人可以选择时，游戏结束，得分高者获胜。
- 现在请你计算出，在两人都使用最佳策略的情况下，谁会获胜（或者判断为平局）。
- (n le 2 imes 10^3)，(m le 10^5)，(|p_i| le 10^9)。
思路
首先跑两次单元最短路径，求出点 (x) 到 (s) 和 (t) 的距离 (dis1_x,dis2_x)。
因为这道题只关心距离的大小关系，所以可以把 (dis1,dis2) 分别离散化一下。然后点 (x) 就对应到一个 (n imes n) 的网格的 ((dis1_x,dis2_x)) 处。
那么此时先手就是取顶部的若干行，后手就是取左侧的若干列。
记 (f[0/1][i][j]) 表示现在到先手/后手取，先手取到第 (i) 行，后手取到第 (j) 列，此时先手权值减去后手权值的最大/最小值。
直接正着 dp 可能会把对方非最优的情况计算到自己最优的情况中（也就是对方不走这个方案，但是转移的时候你的最优方案从对方这个不选的方案转移过来），并且有两种结束状态。所以考虑倒过来 dp。
拿 (f[0][i][j]) 为例，如果 ((i,j)) 到 ((i,n)) 这个子矩阵内至少有一个点，那么
[f[0][i][j]=max(f[0][i+1][j],f[1][i+1][j])+ ext{calc}(i,j,i,n)
]
否则
[f[0][i][j]=f[0][i+1][j]
]
最后只需要看 (f[0][1][1]) 的正负性即可。
时间复杂度 (O(n^2))。
代码
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=2010,M=200010;
int n,m,s,t,tot,c1,c2,a[N],head[N],cnt[N][N];
ll sum[N][N],dis1[N],dis2[N],b[N],c[N],f[2][N][N];
bool vis[N];
struct edge
{
int next,to,dis;
}e[M];
void add(int from,int to,int dis)
{
e[++tot]=(edge){head[from],to,dis};
head[from]=tot;
}
void dij(int s,ll *dis)
{
memset(vis,0,sizeof(vis));
priority_queue<pair<ll,int> > q;
q.push(mp(0,s)); dis[s]=0;
while (q.size())
{
int u=q.top().se; q.pop();
if (vis[u]) continue;
vis[u]=1;
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (dis[v]>dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis;
q.push(mp(-dis[v],v));
}
}
}
}
int calc1(int x,int y,int xx,int yy)
{
return cnt[xx][yy]-cnt[xx][y-1]-cnt[x-1][yy]+cnt[x-1][y-1];
}
ll calc2(int x,int y,int xx,int yy)
{
return sum[xx][yy]-sum[xx][y-1]-sum[x-1][yy]+sum[x-1][y-1];
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
memset(dis1,0x3f3f3f3f,sizeof(dis1));
memset(dis2,0x3f3f3f3f,sizeof(dis2));
dij(s,dis1); dij(t,dis2);
for (int i=1;i<=n;i++)
b[i]=dis1[i],c[i]=dis2[i];
sort(b+1,b+1+n);
c1=unique(b+1,b+1+n)-b-1;
sort(c+1,c+1+n);
c2=unique(c+1,c+1+n)-c-1;
for (int i=1;i<=n;i++)
{
int x=lower_bound(b+1,b+1+c1,dis1[i])-b;
int y=lower_bound(c+1,c+1+c2,dis2[i])-c;
sum[x][y]+=a[i]; cnt[x][y]++;
}
for (int i=1;i<=c1+1;i++)
for (int j=1;j<=c2+1;j++)
{
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
cnt[i][j]+=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
}
for (int i=c1+1;i>=1;i--)
for (int j=c2+1;j>=1;j--)
{
if (i==c1+1 && j==c2+1) continue;
if (!calc1(i,j,i,c2)) f[0][i][j]=f[0][i+1][j];
else f[0][i][j]=max(f[0][i+1][j],f[1][i+1][j])+calc2(i,j,i,c2);
if (!calc1(i,j,c1,j)) f[1][i][j]=f[1][i][j+1];
else f[1][i][j]=min(f[0][i][j+1],f[1][i][j+1])-calc2(i,j,c1,j);
}
if (!f[0][1][1]) cout<<"Flowers";
if (f[0][1][1]>0) cout<<"Break a heart";
if (f[0][1][1]<0) cout<<"Cry";
return 0;
}