【HDU 6891】Chess Class 貪心+寬搜

【HDU 6891】Chess Class 貪心+寬搜

【題意】

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

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

【做法】

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

​ 首先選擇圖中一個點權最大的點$u$，當$u$作為起點時，答案$w_u$一定是$u$的點權$a_u$。

​ 接下來，考慮能夠走到$u$其他點。

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

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

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

演演算法流程：

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

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

​ 因為每個點只會被染色一次，每條邊最多隻會被遍歷一次，因此複雜度$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;
}