【HDU 6891】Chess Class 貪心+寬搜

【HDU 6891】Chess Class 貪心+寬搜

【題意】

? 給出一個 n n n點 m m m邊的有向圖，每個點有一個點權 a i a_i ai?，且至少有一個出度，將點集 V V V劃分為兩個集合 A , B A,B A,B，剛開始，已知有一顆棋子在起點 s s s，玩家1首先操作，將集合 A A A中的點的出邊進行洗掉，使得其中每個點保留且僅保留一條出邊，然后玩家2再操作，將集合 B B B中的點的出邊進行洗掉，使得其中每個點保留且僅保留一條出邊，之后，棋子開始沿著出邊移動，形成一條路徑，該路徑覆寫的所有點的點權最大值就是該次游戲的結果值 w w w，

? 玩家1的目標是使得 w w w盡可能大，玩家2的目標是使得 w w w盡可能小，兩個玩家均使用最優策略，問，當起點 s = i ( 1 ≤ i ≤ n ) s=i(1\leq i \leq n) s=i(1≤i≤n)的時候，對應的 w w w值是多少，

【做法】

? 看似是博弈論，實則可以貪心處理，兩名玩家均使用最優策略，因此他們都能夠推算出對手的策略，

? 首先選擇圖中一個點權最大的點 u u u，當 u u u作為起點時，答案 w u w_u wu?一定是 u u u的點權 a u a_u au?，

? 接下來，考慮能夠走到 u u u其他點，

• 假如 v v v有一條走向 u u u的邊，且 v ∈ A v\in A v∈A，那么當 v v v作為起點時，答案 w v w_v wv?也就是 a u a_u au?了，因為玩家1一定會保留這條邊，讓棋子從 v v v出發后走向 u u u，這樣就一定能獲得最大值，這個時候，點 v v v等效于點 u u u了，可以進一步考慮能走到 v v v的其他點……
• 假如 v v v有一條走向 u u u的邊，且 v ∈ B v\in B v∈B，也就是說， v v v的出度歸玩家2操控，那么玩家2肯定不會選擇保留從 v v v走到 u u u的邊，因為如果保留了， w v w_v wv?就會是當前的最大值，這顯然不是玩家2的一個最優策略，因此，可以洗掉掉 v v v的這條出邊，但是有一種例外，如果在洗掉之前， v v v僅剩這一條出邊了，按照游戲規則，刪不得，因此這個時候和上面的情況一致，答案 w v w_v wv?就是 a u a_u au?了，這個時候，點 v v v也等效于點 u u u了，可以進一步考慮能走到 v v v的其他點……，

? 這樣的操作其實是一個用當前最大點權向其他點染色的程序，染過的點的答案就定下來了，如果染色不能再傳遞了，而還有點沒有被染色，這個時候，未染色部分已經沒有指向染色部分的出邊了，因為之前染色的時候遇到的點，如果不能傳遞，就會刪掉出邊，否則就會傳遞，按照這個規則下去，染色終止的時候，未染色部分沒有指向染色部分的出邊，

? 接下來，就把已染色部分忽視掉，把未染色部分的圖看成一個同類問題，不斷進行上面的步驟，直至所有點染上色，

演算法流程：

? 每次從沒有求出答案的點中選出點權最大的點，將其答案定為它的權值，

? 然后從這個點開始沿反邊寬搜，搜到的第一類點直接傳遞答案然后入隊，搜到的第二類點的出度減一，如果此時出度為0了，也直接傳遞答案然后入隊，否則不做操作，
? 重復上述流程直到所有點都求出答案，

? 因為每個點只會被染色一次，每條邊最多只會被遍歷一次，因此復雜度 O ( n + m ) O(n+m) O(n+m)，

? (不過寫的時候偷懶用了優先佇列（實際可以用鏈表來存每個點權值對應了哪些點），因此下面的演算法實作多了個log)

#define George_Plover
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#define MAXN 500001
using namespace std;
int T,n,m,R,B;
int tot,pre[MAXN],to[MAXN],lin[MAXN];
int w[MAXN],in[MAXN];
bool b_set[MAXN],vis[MAXN];
int ans[MAXN];
priority_queue<pair<int,int> >q;
queue<int> h;
void add(int x,int y)
{
    tot++;lin[tot]=pre[x];pre[x]=tot;to[tot]=y;
}
void init()
{
    tot=0;
    for(int i=1;i<=n;i++)
    {
        pre[i]=0;
        in[i]=0;
        b_set[i]=vis[i]=0;
    }
}
int Case;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&R,&B);
        printf("Case #%d:\n",++Case);
        init();
        for(int i=1;i<=B;i++)
        {
            int tx;
            scanf("%d",&tx);
            b_set[tx]=1;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
            q.push(make_pair(w[i],i));
        }
        for(int i=1;i<=m;i++)
        {
            int tx,ty;
            scanf("%d%d",&tx,&ty);
            add(ty,tx);
            in[tx]++;
        }
        
        while(!q.empty())
        {
            auto u=q.top();q.pop();
            while(!q.empty() && vis[u.second])
            {
                u=q.top();q.pop();
            }
            if(q.empty())break;
            
            vis[u.second]=1;
            ans[u.second]=u.first;
            
            h.push(u.second);
            
            while(!h.empty())
            {
                int x=h.front();h.pop();
                for(int i=pre[x];i;i=lin[i])
                {
                    int v=to[i];
                    if(vis[v])continue;
                    if(!b_set[v])
                        in[v]--;
                    if(b_set[v]||!in[v])
                    {
                        vis[v]=1;
                        ans[v]=ans[x];
                        h.push(v);
                    }
                    
                }
            }
        }
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i],i==n?'\n':' ');   
    }    
    return 0;
}