题目链接：https://atcoder.jp/contests/agc043/tasks/agc043_c

题目大意：给三张无向图 $X,Y,Z$，满足点数为 $n$ ，边数分别为 $M_1,M_2,M_3$ ，然后构造一个点数为 $N^3$ 的图，满足其中的节点 $(x,y,z)$ 。

且其中的边为：

若 $(x_1,x_2)\in E_X$ ，则 $\forall y,z:((x_1,y,z),(x_2,y,z))\in E$

对于 $E_Y,E_Z$ 同理。

然后点 $(x,y,z)$ 的权值为 $10^{18(x+y+z)}$ ，问最大权值和的独立集的最大权值和是多少。

做法

注意到 $10^{18(x+y+z)}=10^{18x}10^{18y}10^{18z}$ ，由于 $10^{18}$ 很大，所以可以注意到两个独立集权值的比较，可以看成是 $(x+y+z)$ 从大到小排序后比较数组字典序。

首先不难证明一个结论（由于和相同的点不会互相删除，所以直接用贪心的思路证明就行了）：

一个独立集是最优解，当且仅当所有点 $(x,y,z)$ 要么在独立集里，要么存在 $(x’,y’,z’)(x’+y’+z’\ge x+y+z)$ 在独立集里且与他有连边。

因此只要能构造出这样的独立集就行了。

在构造的过程中，我们可以发现图中同时有一些点总是同时存在。

什么意思呢？我们将每条边从大到小连边，然后每次将这个 DAG 中入度为 $0$ 的点作为一个集合，然后在 DAG 上删除这个集合，重复这个过程。可以发现，每个集合中的点总是同时存在不妨按照时间顺序给每个集合编号：$X_1,X_2,X_3…$ ，则 $\forall i<j:\forall x\in X_j:\exists y\in X_i:y\to x$ 。

从而知道 $X$ 集合的至多 $O(\sqrt{m})$ 个，同理 $Y$ 集合和 $Z$ 集合也是。

现在可以将原来的 $X,Y,Z$ 图等价的同构成由 $\{X_i\},\{Y_i\},\{Z_i\}$ 构成的图，其中每个图都是 $i\to j(iX_j(i<j)$ （从上面的构造不难看出）。

由于此时的点数只有 $m\sqrt{m}$ ，直接暴力枚举就行了，可以证明此时得到的解在原图上一定满足上面说的是最优解的条件，所以我们就得到了最优解。

时间复杂度：$O(m\sqrt{m})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
typedef long long  LL;
const int N = 1e5 + 5;
const int B = 455;
const LL mod = 998244353, base = (LL)1e18 % mod;
vector<LL> val[3];
bool vis[B][B][B];
LL f[N];
int n, m;
bool v[N];
vector<int> out[N];
void init(){
    f[0] = 1ll; for(int i = 1; i <= n; i++) f[i] = f[i - 1] * base % mod;
}
void solve(int id){
    cin >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        if(x < y) swap(x, y);
        out[x].push_back(y);
    }
    vector<int> pos;
    for(int i = n; i >= 1; i--) pos.push_back(i);
    while(!pos.empty()){
        vector<int> tmp;
        LL now = 0ll;
        for(auto x : pos){
            if(!v[x]){
                now = (now + f[x]) % mod;
                for(auto y : out[x]) v[y] = 1;
            }
            else tmp.push_back(x);
        }
        val[id].push_back(now);
        swap(pos, tmp);
        for(auto x : pos) v[x] = 0;
    }
    for(int i = 1; i <= n; i++) v[i] = 0, out[i].clear();
    assert(val[id].size() <= B);
}
int main(){
    cin >> n;
    init();
    for(int t = 0; t <= 2; t++) solve(t);
    LL ans = 0ll;
    for(int sum = 0; sum + 3 <= val[0].size() + val[1].size() + val[2].size(); sum++){
        for(int i = 0; i <= sum && i < val[0].size(); i++){
            for(int j = 0 ; i + j <= sum && j < val[1].size(); j++){
                int k = sum - i - j;
                if(k >= val[2].size() || vis[i][j][k]) continue;
                ans = (ans + val[0][i] * val[1][j] % mod * val[2][k]) % mod;
                for(int t = i + 1; t < val[0].size(); t++) vis[t][j][k] = 1;
                for(int t = j + 1; t < val[1].size(); t++) vis[i][t][k] = 1;
                for(int t = k + 1; t < val[2].size(); t++) vis[i][j][t] = 1;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}
官方做法

吐槽：不是哥们，我怎么又嗯做做出来一道题目啊。

这道题目的正经做法是这样子的：

注意到最优方案一定是每次选可选的 $i+j+k$ 中最大的，我们可以对边定向，由小指向大，那么可以注意到我们能选到的点当且仅当，将这个图当成一个博弈状态图，这个点是一个必败态。

然后又注意到这其实是三个图的的组合游戏，所以就是异或。

直接求一下 SG 函数，然后不难发现，一个图中的 SG 的上限是根号的，所以直接 $O(m)$ 求一下就行了。

总时间复杂度：$O(n+m)$ 。

反思：

回到我的做法中，我把每个小图中的某些点归为一类，那么这个分类代表什么呢？我当时觉得这玩意可能有实际意义，但是当时我没有看出来。

没看出来的一个很重要的原因：我只对小图求了等价类，但是没有对大图做等价类，因此没有注意到大图的等价类就是小图等价类的组合这个性质。

还有一个很重要的原因：我的建图是从大指向小的。

只能说做题确实需要建模，这题目基本只要想出和 SG 的联系基本就做完了。但是我觉得这并不是我的问题，因为我确实想不到其和 SG 的联系。不能说没有建，只能说建不出来，不是方法问题，是实力问题。

就这样吧，我觉得目前来看，在我的思考过程中，方法没有问题，要真要说优化的话，只能说希望下次做类似的题能做的快一点吧，其余没啥了。

收获：

已知现在有几个有向图游戏，那么这多个游戏同时进行，既可以表示成每个游戏上你都在一个点上，然后每次移动一个点，其意义就是多个游戏同时进行，例子：多个石堆，每次只能在一个石堆上移除石子；也可以像这道题目一样，用 $(x_1,x_2,…,x_n)$ 来表示，边也像这道题目一样标，其意义为直接将这多个游戏同时进行的这场游戏视为一个整体，一个有向图游戏。

这道题目给我的收获就是：发现多个同时进行的有向图游戏还可以用后面那种表示，同时也加深了一下我对有向图游戏的理解。

我认为这是一道好题。