[CF 536D] Tavas in Kansas

作法：

首先先處理出給定的兩個點到其他所有點的距離。再來把到第一個點的距離們和到第二個點的距離們分別離散化，假設總共有 n 種到第一個點的距離， m 種到第二個點的距離，那麼考慮一張 n * m 的方格表（左上角是 ( 1 , 1 ) ，右下角是 ( n , m )），如果在原本的圖中有一個點到給定的兩個點的距離分別是 x1 和 y1 （已經離散化過了，所以 1 <= x1 <= n 且 1 <= y1 <= m），那麼就把這個方格表的 ( x,y ) 位置的價值加上這個點的點權。那麼這個遊戲就可以等價成：先手首先選一個 y0 ，把 y 座標 <= y0 的格子都取走，然後換後手選一個 x0 ，把 x 座標 <= x0 的格子都取走，一直重複這個動作直到格子被取完為止，取的點權和比較多的人就贏了。

但這裡我們還少考慮到了一個東西，就是題目有要求每次必須要至少選到原圖中的一個點，不過我們先思考不考慮那件事的情形。那麼這時就顯然是一個 DP ，記 dp1[ i ][ j ] 代表盤面剩下 ( i , j ) ~ (  n , m ) ，且此時輪到先手時先手可以獲得幾分， dp2[ i ][ j ] 則是此時輪到後手時後手可以獲得幾分，並且記 ( i , j ) ~ ( n , m ) 的分數總和為 S，那麼 dp1[ i ][ j ] 就會等於 S - min{ dp2[ i ][ k ] } , k = j+1 , ... , m+1 （註：當 k = m+1 時代表此時盤面為空）。同理 dp2[ i ][ j ] 的轉移式也類似，而這樣的轉移可以藉由維護好 min{ dp2[ i ][ k ] } 的方法來把複雜度降為 O( nm) 。具體來說，考慮按照從第 n 列做到第1列，同列時從第 m 行作到一行的順序計算每個 DP 值，那麼在算 dp1[ i ][ j ] 的時候，我們需要的值是 min{ dp2[ i ][ j+1 ] , ... , dp2[ i ][ m+1 ] } ， 因此只要紀錄一個值 miy ，代表我們需要的值，並且在算完 dp2[ i ][ j ]的時候拿他去更新 miy 就好了，並且在我們計算到下一列的時候把 miy 的值清掉，就可以繼續用了。同理在算 dp2[ i ][ j ] 的時候，需要的會是 min{ dp1[ i+1 ][ j ] , ... , dp1[ n ][ j ] } ，但這時由於我們計算的順序不是直的，所以不能像剛才一樣只用一個值來維護，必須用一個陣列，也就是每次在算 dp2[ i ][ j ] 需要的值會是 mix[ j ]，並且在算完 dp1[ i ][ j ] 之後把 mix[ j ] 用 dp1[ i ][ j ] 取 min ，維護好他的值。

上面成功解決了弱化版的問題，接下來要把題目原始的條件考慮進來。首先如果當前的狀態是 ( i , j ) ，並且輪到先手，設先手在這一局吃掉的矩形是 ( i , j ) ~ ( n , y0 ) ，那麼為了要讓這一步是合法的，就必須要有這個矩形裡面有至少一個原始圖中的點。但不能直接用這塊矩形的價值總和是否為 0 來判斷，因為題目裡也有提醒點權有可能是 0 ，因此還必須在另外處理一個 val 陣列，其中 val[ i ][ j ] 在 ( i , j ) 有對應到原圖中的一個點時其值為 1 ，否則為 0 ，並且處理出他的二維前綴和陣列，那麼就可以 O( 1 ) 知道這一步合不合法了。再來則是轉移的部份必須要更改，首先看 dp1[ i ][ j ] 的部份，在之前的情況是他可以轉移到 ( i , j+1 ) , ... , ( i , m ) ，但在這裡則不行，因為如果 ( i , j ) 到 ( n , y0 ) 的 val 總和是 0 的話，就會沒辦法轉移到 ( i , y0+1 ) ，但一個簡單的觀察是，如果 ( i , j ) 可以轉移到 ( i , y0 ) ，那麼就可以轉移到 ( i , y1 ) ，其中 y1 >= y0 ，因此我們可以用類似雙指標的方法，多紀錄一個 id 值，代表當前的 miy 的值等於 min{ dp2[ i ][ id+1 ] , dp2[ i ][ id+2 ] , ... , dp2[ i ][ m+1 ] } ，其中 id 代表的意義是「讓 ( i , j ) , ( n , id ) 形成的矩形內的 val 值總和不為 0 的最小值」，那麼就可以維護好 miy 值了。而在算 dp2[ i ][ j ] 的部份就幾乎一樣了，差別只有在和剛剛一樣的 mix 值會變成一個陣列，還有 id 值也會而已了。最後算出的 dp1[ 1 ][ 1 ] 就是先手能夠獲得的分數了。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF (1LL<<60)
using namespace std;
const int maxn=2000+10 ;
 
struct P{int to,dis;};
vector<P> v[maxn] ;
 
struct Q
{
    int id ; LL dis ;
    bool operator < (const Q &rhs) const
    {
        return dis>rhs.dis ;
    }
};
 
priority_queue<Q> pq ;
bool done[maxn] ;
void Dijkstra(int st,LL *d)
{
    fill(d,d+maxn,INF) ;
    d[st]=0 ; pq.push((Q){st,0}) ;
    memset(done,0,sizeof(done)) ;
    while(!pq.empty())
    {
        Q u=pq.top() ; pq.pop() ;
        if(done[u.id]) continue ;
        done[u.id]=1 ;
        for(auto i : v[u.id]) if(d[i.to]>d[u.id]+i.dis)
            d[i.to]=d[u.id]+i.dis , pq.push((Q){i.to,d[i.to]}) ;
    }
}
 
LL d1[maxn],d2[maxn] ;
vector<LL> vx,vy ;
 
LL S(int x1,int y1,int x2,int y2,LL a[maxn][maxn])
{
    return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1] ;
}
 
int w[maxn] ;
LL sum[maxn][maxn] ;
LL dp1[maxn][maxn],dp2[maxn][maxn],val[maxn][maxn] ;
LL mix[maxn] ;
int nowx[maxn] ;
 
main()
{
    int n,m,s,e ; scanf("%d%d%d%d",&n,&m,&s,&e) ;
    for(int i=1;i<=n;i++) scanf("%d",&w[i]) ;
    while(m--)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        v[x].push_back((P){y,dis}) ;
        v[y].push_back((P){x,dis}) ;
    }
 
    Dijkstra(s,d1) ;
    Dijkstra(e,d2) ;
    for(int i=1;i<=n;i++) vx.push_back(d1[i]) , vy.push_back(d2[i]) ;
    sort(vx.begin(),vx.end()) ;
    sort(vy.begin(),vy.end()) ;
    vx.resize(unique(vx.begin(),vx.end())-vx.begin()) ;
    vy.resize(unique(vy.begin(),vy.end())-vy.begin()) ;
    int sx=vy.size() , sy=vx.size() ;
 
    for(int i=1;i<=n;i++)
    {
        int x=lower_bound(vx.begin(),vx.end(),d1[i])-vx.begin()+1 ;
        int y=lower_bound(vy.begin(),vy.end(),d2[i])-vy.begin()+1 ;
        val[y][x]=1 ; sum[y][x]+=w[i] ;
    }
    for(int i=1;i<=sx;i++) for(int j=1;j<=sy;j++)
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j] ,
        val[i][j]=val[i-1][j]+val[i][j-1]-val[i-1][j-1]+val[i][j] ;
 
    for(int i=1;i<=sy;i++) mix[i]=INF , nowx[i]=sx ;
 
    LL miy=INF ;
    for(int i=sx;i>=1;i--) for(int j=sy,nowy=sy;j>=1;j--)
    {
        if(j==sy) miy=INF ;
        if(S(i,j,sx,j,val)) while(nowy>=j)
        {
            miy=min(miy,dp2[i][nowy+1]) ;
            nowy-- ;
        }
        if(S(i,j,i,sy,val)) while(nowx[j]>=i)
        {
            mix[j]=min(mix[j],dp1[nowx[j]+1][j]) ;
            nowx[j]-- ;
        }
 
        if(miy!=INF) dp1[i][j]=S(i,j,sx,sy,sum)-miy ;
        if(mix[j]!=INF) dp2[i][j]=S(i,j,sx,sy,sum)-mix[j] ;
    }
 
    LL ans=dp1[1][1] , all=S(1,1,sx,sy,sum) ;
    if(2*ans==all) printf("Flowers\n") ;
    else if(2*ans<all) printf("Cry\n") ;
    else printf("Break a heart\n") ;
}