Fork me on GitHub

Codeforces536D

Codeforces536D题解

题意:

  • 给你一张$n$个点$m$条边的无向图,每个点有一个点权$p_i$(存在负数)
  • 有两个人在进行游戏,他们分别在$s$、$t$号点。
  • 两个人轮流操作,每次操作选出一个非负整数$x$,表示将到他们所在点最短距离小于等于$x$的点的点权拿走。(拿走后点权消失,且每次拿走的有点权的点的个数至少为1)
  • 询问最后胜负情况(谁的总点权和较大)。
  • $n \leq 2000,n-1 \leq m \leq 100000$

题解:

  • 首先跑最短路得出每个点到$s$、$t$的最短距离$ds[i],dt[i]$。
  • 然后问题转化为二维空间上有$n$个点$(ds[i],dt[i])$,每次每个人选择平行于$x$轴或$y$轴的直线,将在它左方或者下方的点拿走,并保证每次至少拿走一个点。
  • 首先可以离散化。
  • 然后按时间从晚到早进行转移。
  • $dp[i][j][k]$代表在第$k$个人某次操作前,已经拿走的点是在$(i,j)$左下方的点的最大或者最小点权差,根据$dp[0][0][0]$正负可以判断最终胜负。
  • 然后可以进行一行一列的转移,讨论一下这行是否有点或者是否是某次选择的第一行或第一列就行了。
  • 时间复杂度$O((n+m)logn+n^2)$

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 2009
#define inf 0x3f
using namespace std;
ll n,m,s,t,dis[N],Dis[N],vis[N],r,c,val[N],f[N][N];
ll S[N][N],T[N][N],dp[N][N][2];
vector <ll> X,Y;
int main()
{
#ifdef ONLINE_JUDGE
bool lych_cys_is_zero=true,miaom_is_zero=true;
#else
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>s>>t;
for (ll i=1;i<=n;i++) cin>>val[i];
memset(f,inf,sizeof(f));
for (ll i=1;i<=m;i++)
{
ll x,y,z;
cin>>x>>y>>z;
f[x][y]=f[y][x]=min(z,f[x][y]);
}
memset(dis,inf,sizeof(dis));
memset(Dis,inf,sizeof(Dis));
dis[s]=Dis[t]=0;
memset(vis,0,sizeof(vis));
for (ll i=1;i<=n;i++)
{
ll k=-1;
for (ll j=1;j<=n;j++)
if (!vis[j]&&(dis[j]<dis[k]||k==-1)) k=j;
vis[k]=1;
for (ll j=1;j<=n;j++)
if (!vis[j]&&f[k][j]<(ll)1e18&&dis[k]+f[k][j]<dis[j]) dis[j]=dis[k]+f[k][j];
}
memset(vis,0,sizeof(vis));
for (ll i=1;i<=n;i++)
{
ll k=-1;
for (ll j=1;j<=n;j++)
if (!vis[j]&&(Dis[j]<Dis[k]||k==-1)) k=j;
vis[k]=1;
for (ll j=1;j<=n;j++)
if (!vis[j]&&f[k][j]<(ll)1e18&&Dis[k]+f[k][j]<Dis[j]) Dis[j]=Dis[k]+f[k][j];
}
X.clear(),Y.clear();
for (ll i=1;i<=n;i++) X.push_back(dis[i]),Y.push_back(Dis[i]);
sort(X.begin(),X.end()),sort(Y.begin(),Y.end());
X.resize(unique(X.begin(),X.end())-X.begin());
Y.resize(unique(Y.begin(),Y.end())-Y.begin());
memset(S,0,sizeof(S));
memset(T,0,sizeof(T));
memset(dp,0,sizeof(dp));
for (ll i=1;i<=n;i++)
{
dis[i]=lower_bound(X.begin(),X.end(),dis[i])-X.begin()+1;
Dis[i]=lower_bound(Y.begin(),Y.end(),Dis[i])-Y.begin()+1;
S[dis[i]][Dis[i]]+=val[i],T[dis[i]][Dis[i]]++;
}
for (int i=1;i<=n;i++)
{
cerr<<dis[i]<<" "<<Dis[i]<<endl;
}
n++;
for (ll i=1;i<=n;i++)
for (ll j=1;j<=n;j++)
{
S[i][j]+=S[i-1][j]+S[i][j-1]-S[i-1][j-1];
T[i][j]+=T[i-1][j]+T[i][j-1]-T[i-1][j-1];
}
for (ll i=n-1;i>=0;i--)
for (ll j=n-1;j>=0;j--)
{
if (T[i+1][n]-T[i][n]-T[i+1][j]+T[i][j]==0)
dp[i][j][0]=dp[i+1][j][0];
else
dp[i][j][0]=max(dp[i+1][j][0],dp[i+1][j][1])+S[i+1][n]-S[i][n]-S[i+1][j]+S[i][j];
if (T[n][j+1]-T[n][j]-T[i][j+1]+T[i][j]==0)
dp[i][j][1]=dp[i][j+1][1];
else
dp[i][j][1]=min(dp[i][j+1][1],dp[i][j+1][0])-S[n][j+1]+S[n][j]+S[i][j+1]-S[i][j];
}
cerr<<dp[0][0][0]<<endl;
if (dp[0][0][0]>0) cout<<"Break a heart"<<endl;
else if (dp[0][0][0]<0) cout<<"Cry"<<endl;
else cout<<"Flowers"<<endl;
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces536D

文章作者:wzf2000

发布时间:2017年12月25日 - 12:12

最后更新:2017年12月26日 - 05:12

原始链接:https://wzf2000.github.io/2017/12/25/Codeforces536D/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。