图论+博弈论上dp：CF536D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133364509

此题其实比较板，只是我没看出来

首先肯定要跑个最短路，然后发现可以离散化把值域缩小

然后 nn 很小，直接暴力列个 n2n^2 dp。

转移要注意的是必须从大往小dp。从小到大会产生后效性。

然后拿个双指针优化下转移就行。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// LUOGU_RID: 126383363
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 2010
//#define M
//#define mo
struct node {
	int y, w; 
};
int n, m, i, j, k, T;
priority_queue<pair<int, int> >q; 
int sum[N][N], cnt[N][N], s1[N], s2[N], f[N][N][2], x, y, u, v, w; 
int z[N], vis[N], val[N], st, ed, mn, mn1[N], mn2[N], o1[N], o2[N]; 
vector<node>G[N]; 

void dij(int s, int ans[N]) {
	for(i=1; i<=n; ++i) ans[i]=1e18; 
	q.push({0, s}); ans[s]=0; 
	while(!q.empty()) {
		u=q.top().second; q.pop(); 
		for(auto t : G[u]) {
			v=t.y; 
//			printf("%d -> ")
			if(ans[u]+t.w<ans[v]) {
				ans[v]=ans[u]+t.w; 
				q.push({ans[v], v}); 
			}
		}
	}
	for(i=1; i<=n; ++i) z[i]=ans[i]; 
//	for(i=1; i<=n; ++i) printf("%lld ", ans[i]); printf("\n"); 

	sort(z+1, z+n+1); 
	for(i=1; i<=n; ++i) ans[i]=lower_bound(z+1, z+n+1, ans[i])-z; 
}

void calc(int sum[N][N]) {
	for(i=0; i<=n; ++i) {
		for(j=1; j<=n; ++j) vis[j]=0; 
		for(j=1; j<=n; ++j) 
			if(s1[j]<=i) vis[j]=1, sum[i][0]+=val[j]; 
		for(j=1; j<=n; ++j) if(!vis[j]) sum[i][s2[j]]+=val[j]; 
		for(j=1; j<=n; ++j) sum[i][j]+=sum[i][j-1]; 
	}
	int num=sum[n][n]; 
	for(i=0; i<=n; ++i) for(j=0; j<=n; ++j) sum[i][j]=num-sum[i][j]; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); st=read(); ed=read(); 
	for(i=1; i<=n; ++i) val[i]=read(); 
	for(i=1; i<=m; ++i) {
		u=read(); v=read(); w=read(); 
		G[u].pb({v, w}); G[v].pb({u, w}); 
	}
	k=0; dij(st, s1); dij(ed, s2); 
//	for(i=1; i<=n; ++i) printf("%lld ", s1[i]); printf("\n"); 
//	for(i=1; i<=n; ++i) printf("%lld ", s2[i]); printf("\n"); 
	calc(sum); fill(val+1, val+n+1, 1); calc(cnt); 
	memset(f, 0x80, sizeof(f)); 
	for(i=0; i<=n; ++i) 
		o1[i]=o2[i]=n, mn1[i]=mn2[i]=1e18; 
	for(i=n; i>=0; --i)
	 	for(j=n; j>=0; --j) {
	 		if(cnt[i][j]==0) {
	 			f[i][j][0]=f[i][j][1]=0;  continue; 
			 }
			 
			for(int &k=o1[j]; k>i && cnt[k][j]<cnt[i][j]; --k) 
				mn1[j]=min(mn1[j], f[k][j][1]); 
			f[i][j][0]=sum[i][j]-mn1[j]; 
			for(int &k=o2[i]; k>j && cnt[i][k]<cnt[i][j]; --k)
			 	mn2[i]=min(mn2[i], f[i][k][0]); 
			f[i][j][1]=sum[i][j]-mn2[i]; 
			
//			for(k=n, mn=1e18; k>i && cnt[k][j]<cnt[i][j]; --k) 
//				f[i][j][0]=max(f[i][j][0], sum[i][j]-f[k][j][1]); 
//			for(k=n, mn=1e18; k>j && cnt[i][k]<cnt[i][j]; --k)
//			 	f[i][j][1]=max(f[i][j][1], sum[i][j]-f[i][k][0]); 
			 	


//			printf("f[%lld][%lld][0/1]=%lld %lld | %lld %lld %lld %lld\n", i, j, f[i][j][0], f[i][j][1], sum[i][j], mn, cnt[i][j], cnt[2][j]); 
		 }
	x=f[0][0][0], y=sum[0][0]-x; 
//	printf("%lld | %lld %lld\n", sum[0][0], x, y); 
	if(x>y) printf("Break a heart");  	
	else if(y>x) printf("Cry"); 
	else printf("Flowers"); 
	return 0;
}