U548486 决斗 做题笔记

Resstifnurv · 2025-08-12 19:08:24 · 个人记录

好题。

首先考虑对 b 类边建一个反图 G_1 跑拓扑排序，把能入队的节点和边合在一块建一个新的反图 G_2，不难发现 G_2 是一个 DAG。

于是在 G_2 上我们加入所有的 a 类边。对一条 a 类边 e_i:u \rightarrow v，它可以是以下三种情况之一：

1. 前向边。此时 u 可以通过 DAG 上的边直达 v。

2. 返祖边。 此时 v 可以通过 DAG 上的边直达 u。

3. 横跨边。此时 u, v 无法通过 DAG 上的边互通。

注意到前向 a 类边和返祖 a 类边是否发挥作用是已经确定的，所以可以直接拍进 \text{atk} 里然后删掉，于是只有横跨边是需要考虑的。

::::info[那么怎么判断一条 a 类边是否是横跨边呢？]{open} 我口胡了一个非常逆天的做法：

注意到不论是前向边还是返祖边，其两端的节点的拓扑序大小关系是已经确定的，只有横跨边不然。那么我们如果以不同的遍历策略跑多次拓扑排序时，一条 a 类边两端节点的拓扑序大小关系发生了改变，那我们就可以断定这是一条横跨边。

考虑随机化。我们如果使用 std::vector 存图，那么不妨在每次开始遍历子节点时先对该点的 vector 进行 shuffle()。这样，对于一个节点 u 的两个子节点 v, w，v 在 w 之前被遍历的概率与 w 在 v 之前被遍历的概率相同，均为 \Large \frac{1}{2}。为了把这种性质扩展到整个子树，我们把传统拓扑排序使用的队列换成栈，起到类 dfs 的效果。

在这种情况下，考虑一个简化的极端情况：一个 3 个节点的二叉树，2, 3 号节点分别是 1 号节点的左、右儿子，那么按上述逻辑运行 \lceil \text{log}_2M \rceil + 1 = 18 次拓扑排序（在树上就相当于跑 dfs），2, 3 号节点的拓扑序大小关系全部一致的概率只有 \Large \frac{1}{2^{18}}，也即漏判横跨边的概率为 \Large \frac{1}{2^{18}}，这是可以接受的。 ::::

接下来考虑把横跨 a 类边都加进 G_2 里成为 G_3。因为唯一会和 G_2 成环的 a 类边——返祖边——已经被我们删掉了，所以只要 a 类边没有自己成环，那么 G_3 全图就也是一个 DAG。在这种情况下我们在这个 DAG 上直接跑拓扑排序并计算分数就是最优的，因为我们把所有能提前去掉的 a 类边都去掉了。

考虑复杂一点的情况，也就是 a 类边自己就形成了环。易知环内所有点的“等级”必须都一样，那么这也意味着一个点不会同时被包含在两个环内，那么使用 \text{Tarjan} 找环就很方便了。

假如我们找到了一个长度为 n 的环（记为 1 \rightarrow 2 \rightarrow 3 \rightarrow \dots \rightarrow n \rightarrow 1），我们显然没法兼顾这 n 条边，至少需要顶着其中一条边的加持删掉一个点。

• 先考虑一个容易的情况：所有点在 a 类边的加持下 \text{atk} 依然 < 4000，这个时候我们可以随意地选择放弃的那条边，显然可以选择边权值最小的那条边，这样我们的得分损失最少。
• 还有一种情况也是简单的：一个点不管环上指向它的 a 类边是否失效，其 \text{atk} 都 \ge 4000，那我们只需要删掉这个点以及它的所有出入边即可。
• 那如果有的点只有在指向它的 a 类边失效时 \text{atk} 才 \ge 4000 呢？放弃这个点是显然不优的，我们需要为它在环上的入边打上标记，打上标记的边不参与边权的比较，因为它不能被放弃。

这样，去掉由 a 类边组成的环上的一边，我们就可以保证最后合成的 G_3 是一个 DAG 了，直接模拟即可。

::::info[code]

// U548486 决斗
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>

using namespace std;
using pii = pair<int, int>;
#define mp make_pair

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int DRA_ATK = 4000;

namespace fastIO{

#ifdef ONLINE_JUDGE
#define gch getchar_unlocked
#define pch putchar_unlocked
#endif

#ifndef ONLINE_JUDGE
#define gch getchar
#define pch putchar
#endif

    inline int read(){
        int ret = 0;
        char ch = ' ', c = gch();
        while(!('0' <= c && c <= '9')) ch = c, c = gch();
        while('0' <= c && c <= '9') ret = ret * 10 + (c ^ 48), c = gch();
        return ch == '-' ? -ret : ret;
    }

    char stk[100], tt = -1;
    inline void write(int x, char end = '\n'){
        if(x == 0){ pch('0'); pch(end); return ;}
        if(x >> 31) pch('-'), x = -x;
        while(x){
            stk[++tt] = x % 10 + 48;
            x /= 10;
        }
        while(~tt) pch(stk[tt--]);
        pch(end);
    }
}

class graph_base;
class graph_1;
class graph_2;
class graph_3;
class graph_4;
class edge_base;
class edge_1;
class edge_2;
vector<edge_1> e_a;
vector<edge_2> e_a_cross;

int pt_val[N];
stack<int> stk;

class graph_base{
public:
    int n;
    vector<int> to[N];
    int deg[N];
    inline void add(int x, int y){
        to[x].push_back(y);
        deg[y]++;
    }
};

class graph_1 : public graph_base{
// G1 仅用来存储 b 类边的反图并进行拓扑排序，以构建 G2。
public:
    vector<int> to_inv[N];
    inline void add_inv(int x, int y){
        to_inv[y].push_back(x);
    }

    void toposort(graph_2 &G2){
        for(int i = 1; i <= n; i++){
            if(!deg[i]) stk.push(i);
        }
        while(!stk.empty()){
            int u = stk.top(); stk.pop();
            for(auto v: to[u]){
                if(--deg[v]) continue;
                stk.push(v);
                for(auto _u: to_inv[v]) G2.add(_u, v);
            }
        }
    }

    inline void clear(){
        for(int i = 1; i <= n; i++){
            to[i].clear();
            deg[i] = 0;
        }
    }
} G1;

class graph_2 : public graph_base{
// G2 存储 b 类边的反图并进行两次拓扑排序，
// 以判定横跨 a 类边并构建 G4。
public:
    int deg_cpy[N];
    inline void cpy_deg(){
        for(int i = 1; i <= n; i++) deg_cpy[i] = deg[i];
    }inline void lod_cpy(){
        for(int i = 1; i <= n; i++) deg[i] = deg_cpy[i];
    }

    int ts = 0, dfn[N];
    void toposort(){
        ts = 0, lod_cpy();
        for(int i = 1; i <= n; i++){
            if(!deg[i]) stk.push(i);
        }
        while(!stk.empty()){
            int u = stk.top(); stk.pop();
            dfn[u] = ++ts;
            for(auto v: to[u]){
                if(--deg[v]) continue;
                stk.push(v);
            }
        }
    }

    void rev_all(){
        for(int i = 1; i <= n; i++)
            reverse(to[i].begin(), to[i].end());
    }

    void check(vector<edge_1> &e){
        toposort();
        for(int i = 0; i < int(e.size()); i++){
            int status = (dfn[e[i].u] < dfn[e[i].v]);
            e[i].type = status;
        }
        rev_all(); toposort();
        for(int i = 0; i < int(e.size()); i++){
            int status = (dfn[e[i].u] < dfn[e[i].v]);
            if(e[i].type ^ status) e[i].type = 0;
            else e[i].type = (status ? +1 : -1);
        }
    }

    inline void clear(){
        for(int i = 1; i <= n; i++){
            to[i].clear();
            deg[i] = deg_cpy[i] = 0;
        }
    }
} G2;

class graph_3 /*: graph_base*/{
// G3 存储 a 类边的正向图并进行 Tarjan 找环删边，
// 以辅助 G4 的构建。
public:
    int n;
    vector<pii> to[N];
    inline void add(int x, int y, int eid){
        to[x].push_back(mp(y, eid));
    }

    int dfn[N], low[N], ts = 0, inid[N];
    bool instk[N];
    vector<int> ring_pt;
    vector<edge_2> ring_ed;

    void tarjan(int u, int id, graph_4 &G4){
        dfn[u] = low[u] = ++ts;
        stk.push(u); instk[u] = true;
        inid[u] = id;
        for(auto [v, eid]: to[u]){
            if(!dfn[v]){
                tarjan(v, eid, G4);
                low[u] = min(low[v], low[u]);
            } else if(instk[v]){
                low[u] = min(low[u], dfn[v]);
            }
        }
        if(dfn[u] == low[u]){
            // 找出环了
            ring_pt.clear(), ring_ed.clear();
            edge_2 minimun_edge, now;
            int minimun_edge_id = -1, t, stk_top = stk.top();
            bool flag = false;
            do{
                t = stk.top(); stk.pop();
                ring_pt.push_back(t);
                if(t == u) break;
                now = e_a_cross[inid[t]];
                if(pt_val[t] >= DRA_ATK){
                    G4.del[t] = true;
                    flag = true;
                    continue;
                } // 情况一，一个点无论是否加上这条边都 >= 4000
                // 这时因为已经删掉了点和它相邻的边，所以打 flag 标记表示不用再额外删边
                else if(pt_val[t] + now.val >= DRA_ATK){
                    now.is_protected = true;
                } // 情况二，这时这条边要被保护起来
                if(now < minimun_edge){
                    minimun_edge = now;
                    minimun_edge_id = int(ring_ed.size());
                } // 情况三，这时这条边可以正常参与比较
                ring_ed.push_back(now);
            } while(t != u);
            for(auto [v, eid]: to[stk_top]){
                if(v != u) continue;
                now = e_a_cross[eid];
                if(pt_val[u] >= DRA_ATK){
                    G4.del[u] = true;
                    flag = true;
                    continue;
                } // 情况一，一个点无论是否加上这条边都 >= 4000
                // 这时因为已经删掉了点和它相邻的边，所以打 flag 标记表示不用再额外删边
                else if(pt_val[u] + now.val >= DRA_ATK){
                    now.is_protected = true;
                } // 情况二，这时这条边要被保护起来
                if(now < minimun_edge){
                    minimun_edge = now;
                    minimun_edge_id = int(ring_ed.size());
                } // 情况三，这时这条边可以正常参与比较
                ring_ed.push_back(now);
                break;
            }
            if(!flag){
                if(id == -1){
                    // 这时说明所有的边都被保护起来，我们找不到突破口
                    // 因此这时环上的所有点都无法被删除
                    for(auto pt: ring_pt) G4.del[pt] = true;
                    return ;
                }
                for(int i = 0; i < int(ring_ed.size()); i++){
                    if(i == minimun_edge_id) continue;
                    now = ring_ed[i];
                    G4.add_a(now.u, now.v, now.val);
                }
            }
            else{
                for(int i = 0; i < int(ring_ed.size()); i++){
                    now = ring_ed[i];
                    G4.add_a(now.u, now.v, now.val);
                }
            }
        }
    }

    void default_tarjan(graph_4 &G4){
        ;
    }

    inline void clear(){
        for(int i = 1; i <= n; i++){
            to[i].clear();
            dfn[i] = low[i] = 0;
        }
        ts = 0;
    }
} G3;

class graph_4 : public graph_base{
// 最终的 DAG，用于进行模拟求出答案。
public:
    bool del[N];
    inline void add_a(int x, int y, int val){
        // 这个函数是给 G3 中没删掉的 a 类边使用的
        // 在筛选出横跨 a 类边之后就先把所有的 atk 加上，
        // 在确定这条边可以不发挥作用之后再减去。
        if(!del[x] && !del[y]){
            add(x, y);
            pt_val[y] -= val;
        }
        // 如果 y 被删除，那么 atk 没有作用了；
        // 如果 x 被删除，那么 y 的 atk 也一定会吃到这条边的加成，也不用动。
    }
    inline void add_b(int x, int y){
        // 这个函数是给 G2 中的 b 类边使用的
        if(del[x] || del[y]){
            if(!del[y]) deg[y]++;
            // 这样可以防止访问到本身没被删除但是上游节点被删除的 y
            return ;
        }
        else add(x, y);
    }

    int toposort(){
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(!deg[i] && pt_val[i] < DRA_ATK) stk.push(i);
        }
        while(!stk.empty()){
            int u = stk.top(); stk.pop();
            ans += DRA_ATK - pt_val[u];
            for(auto v: to[u]){
                if(--deg[v]) continue;
                if(pt_val[v] < DRA_ATK) stk.push(v);
            }
        }
        return ans;
    }

    inline void clear(){
        for(int i = 1; i <= n; i++){
            to[i].clear();
            deg[i] = 0;
            del[i] = false;
        }
    }
} G4;

class edge_base{
public:
    int u, v;
};

class edge_1 : public edge_base{
// 原始的 a 类边，用于判断 a 类边的类型。
public:
    int val, type;
    // type = 1, -1, 0 分别说明是前向边、返祖边、横跨边。
    edge_1(int val, int type){
        this->val = val;
        this->type = type;
    }
};

class edge_2 : public edge_base{
// 横跨 a 类边，用于在 G3 中决定删边。
public:
    int val;
    bool is_protected;
    edge_2(int val = INF, bool is_protected = false){
        this->val = val;
        this->is_protected = is_protected;
    }
    bool operator< (const edge_2 &ed) const{
        if(this->is_protected ^ ed.is_protected)
            return ed.is_protected;
        return this->val < ed.val;
    }
};

void clear_all(){
    G1.clear();
    G2.clear();
    G3.clear();
    G4.clear();
    e_a.clear();
    e_a_cross.clear();
}

void solve(){
    int n = fastIO::read();
    G1.n = G2.n = G3.n = G4.n = n + 1;
    clear_all();
}

int main(){
    int c = fastIO::read(), T = fastIO::read();
    while(T--) solve();
    return 0;
}

::::