【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;
}