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