Tavas in Kansas[CF536D]

发表于 2020-07-04 分类于 CF

链接

题意

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

题解

分析一下可以发现，这两个人博弈所形成的的状态可以由 $(k,i,j)$ 表示，其中 $k$ 表示当前谁先手，第一个人当前的距离是 $i$，第二个人当前的距离是 $j$ 。

因此，先把到 $s$ 和 $t$ 的最短路预处理，然后进行离散化，那么这个状态就是 $O(n^2)$ 级别的了。设第 $i$ 个点在这两个离散化数组中的下标是 $id1_i,id2_i$。

考虑DP，设 $f_{k,i,j}$ 表示状态为 $(k,i,j)$ 时，第一个人减去第二个人的值是多少。设 $sum(i,j,k,l)$ 表示满足 $id1_x\in[i,j],id2_x\in[k,l]$ 的 $x$ 点的权值之和。

那么有：

$$f_{0,i,j}=\max{f_{1,k,j}+sum(i,k-1,j,\infty)|k>i}$$

$$f_{1,i,j}=\min{f_{0,i,k}+sum(i,\infty,j,k-1)|k>j}$$

此外，还需满足每个人每次必须能够至少选定一个城市的条件，也就是必须有至少一个点在里面。

算 $sum$ 可以二维前缀和搞一搞就好。

DP直接暴力是 $O(n^3)$ 的，然后你发现用一个前缀最值优化一下就好了。

时间复杂度 $O(m\log n+n^2)$。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=2010;
const int M=200010;
const ll inf=1e18;
int n,m;
namespace Graph{
	int ver[M],val[M],ne[M],head[N],tot=1;
	inline void add(int x,int y,int z)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=z; ne[tot]=head[y]; head[y]=tot;
	}
	struct node{
		int u; ll d;
		friend inline bool operator<(const node &A,const node &B)
		{
			return A.d>B.d;
		}
	};
	priority_queue<node> q;
	ll h[N],d[N];
	bool vis[N];
	inline void get_dis(int s,int &m,int *id)
	{
		for(;!q.empty();q.pop());
		q.push((node){s,0});
		fo(i,1,n) d[i]=inf,vis[i]=0;
		d[s]=0;
		for(int u;!q.empty();)
		{
			u=q.top().u; q.pop();
			if(vis[u]) continue;
			vis[u]=1;
			for(int i=head[u],v;i;i=ne[i])
				if(d[v=ver[i]]>d[u]+val[i])
				{
					d[v]=d[u]+val[i];
					if(!vis[v]) q.push((node){v,d[v]});
				}
		}
		fo(i,1,n) id[i]=i,h[i]=d[i];
		sort(h+1,h+n+1);
		m=unique(h+1,h+n+1)-h-1;
		fo(i,1,n) id[i]=lower_bound(h+1,h+m+1,d[i])-h;
	}
}
int s,t,p[N];
int ids[N],idt[N],ns,nt;
ll sum[N][N],f[2][N][N];
int siz[N][N];
inline int si(int x,int y,int l,int r)
{
	return siz[l][r]-siz[l][y-1]-siz[x-1][r]+siz[x-1][y-1];
}
inline ll su(int x,int y,int l,int r)
{
	return sum[l][r]-sum[l][y-1]-sum[x-1][r]+sum[x-1][y-1];
}

int main()
{
	n=read(); m=read();
	s=read(); t=read();
	fo(i,1,n) p[i]=read();
	int x,y,z;
	fo(i,1,m) x=read(),y=read(),z=read(),Graph::add(x,y,z);
	Graph::get_dis(s,ns,ids);
	Graph::get_dis(t,nt,idt);
	fo(i,1,n) siz[ids[i]][idt[i]]++,sum[ids[i]][idt[i]]+=p[i];
	fo(i,1,ns)
		fo(j,1,nt)
			siz[i][j]+=siz[i-1][j]+siz[i][j-1]-siz[i-1][j-1],
			sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	fd(i,ns,1)
		fd(j,nt,1)
		{
			if(si(i,j,i,nt)) f[0][i][j]=max(f[0][i+1][j],f[1][i+1][j])+su(i,j,i,nt);
			else f[0][i][j]=f[0][i+1][j];
			if(si(i,j,ns,j)) f[1][i][j]=min(f[1][i][j+1],f[0][i][j+1])-su(i,j,ns,j);
			else f[1][i][j]=f[1][i][j+1];
		}
	if(f[0][1][1]>0) puts("Break a heart");
	else if(f[0][1][1]<0) puts("Cry");
	else puts("Flowers");
	return 0;
}