CF536D Tavas in Kansas

题意

• 给定\(n\)个点\(m\)条边带点权的无向联通图
• A在\(s\)点，B在\(t\)点，每人最初的值为0，每人每次可以选择一个距离\(d\)，将所有与他自己距离不超过\(d\)的点标记
• 然后将自己的值加上本次所有标记了的点的权值，每次至少标记一个点，直到所有点都标记为止，最后值大的人获胜

博弈论，将每个点到另外两点的距离跑出来，然后扔到坐标系里，发现每次选择相当于将每个人的直线向下/右平移，标记所有未标记的点
考虑记\(f_{n, m, 0/1}\)表示当前可以选\(n~N,m~M\)点，先手/后手能得到的最大权值，然后从后往前以及从下往上转移就好了

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 2000
#define maxm 100000
using namespace std;

int n, m, s, t, hd[maxn + 5], len = 0, a[maxn + 5], cnt[2];
LL sum[maxn + 5][maxn  + 5], b[2][maxn + 5], ma[maxn + 5][maxn + 5], f[2][maxn + 5][maxn + 5], mx[maxn + 5], now[maxn + 5];
struct Edge{int v, w, net;} e[2 * maxn + 5];
void add(int u, int v, int w){e[len] = (Edge){v, w, hd[u]}; hd[u] = len++;}

LL dis[2][maxn + 5];
void dij(int x, int ty){
	memset(dis[ty], inf, sizeof dis[ty]); dis[ty][x] = 0;
	priority_queue<pair<LL, int> > q;
	q.push(mp(0, x));
	while(q.size()){
		int u = q.top().sec; q.pop();
		Tra(u, i){
			int v = e[i].v, w = e[i].w;
			if(dis[ty][v] <= dis[ty][u] + w) continue;
			dis[ty][v] = dis[ty][u] + w;
			q.push(mp(-dis[ty][v], v));
		}
	}
}

int main(){
	//freopen("in", "r", stdin);
	memset(hd, -1, sizeof hd);
	scanf("%d %d %d %d", &n, &m, &s, &t);
	For(i, 1, n) scanf("%d", &a[i]);
	For(i, 1, m){
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		add(u, v, w); add(v, u, w);
	}
	
	dij(s, 0);
	For(i, 1, n) b[0][++cnt[0]] = dis[0][i];
	sort(b[0] + 1, b[0] + cnt[0] + 1);
	cnt[0] = unique(b[0] + 1, b[0] + cnt[0] + 1) - b[0] - 1;
	For(i, 1, n) dis[0][i] = lower_bound(b[0] + 1, b[0] + cnt[0] + 1, dis[0][i]) - b[0];

	dij(t, 1);
	For(i, 1, n) b[1][++cnt[1]] = dis[1][i];
	sort(b[1] + 1, b[1] + cnt[1] + 1);
	cnt[1] = unique(b[1] + 1, b[1] + cnt[1] + 1) - b[1] - 1;
	For(i, 1, n) dis[1][i] = lower_bound(b[1] + 1, b[1] + cnt[1] + 1, dis[1][i]) - b[1];

	For(i, 1, n) sum[dis[0][i]][dis[1][i]] += a[i], ma[dis[0][i]][dis[1][i]] = 1;

	/*cout << cnt[0] << " " << cnt[1] << endl;
	For(i, 1, cnt[0]){
		For(j, 1, cnt[1]) cout << sum[i][j] << " ";
		cout << endl;
	}
	cout << endl;*/
	
	Rof(i, cnt[0], 1) Rof(j, cnt[1], 1){
		sum[i][j] += sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1];
		ma[i][j] += ma[i + 1][j] + ma[i][j + 1] - ma[i + 1][j + 1];
	}

	For(i, 1, cnt[1]) now[i] = cnt[0], mx[i] = cnt[0] + 1;
	Rof(i, cnt[0], 1){
		int nowi = cnt[1], mxi = cnt[1] + 1;
		Rof(j, cnt[1], 1){
			while(now[j] > i && ma[i][j] - ma[now[j]][j]){
				if(sum[now[j]][j] - f[1][now[j]][j] + sum[i][j] - sum[now[j]][j] > sum[mx[j]][j] - f[1][mx[j]][j] + sum[i][j] - sum[mx[j]][j]) mx[j] = now[j];
				now[j]--;
			}
			f[0][i][j] = sum[mx[j]][j] - f[1][mx[j]][j] + sum[i][j] - sum[mx[j]][j];
			
			while(nowi > j && ma[i][j] - ma[i][nowi]){
				if(sum[i][nowi] - f[0][i][nowi] + sum[i][j] - sum[i][nowi] >= sum[i][mxi] - f[0][i][mxi] + sum[i][j] - sum[i][mxi]) mxi = nowi;
				nowi--;
			}
			f[1][i][j] = sum[i][mxi] - f[0][i][mxi] + sum[i][j] - sum[i][mxi];
		}
	}
	
	LL tem = f[0][1][1] - (sum[1][1] - f[0][1][1]);
	if(tem > 0) puts("Break a heart");
	else if(tem < 0) puts("Cry");
	else puts("Flowers");
	return 0;
}

CF536D Tavas in Kansas

原文：https://www.cnblogs.com/lprdsb/p/13769458.html