CF 780F Axel and Marston in Bitland

题目描述

https://codeforces.com/problemset/problem/780/F

简要题意：给定一个有向图有自环无重边，边有两种类型 $0$ 和 $1$，求最长路径，如果最长路径大于 $1e18$ 则视为 $-1$，同时走到路径的边的类型有如下限制，$0$，$01$，$0110$，$01101001$，即长度为 $2^n$ 的路径是由长度为 $2^{n-1}$ 的路径和长度为 $2^{n-1}$ 取反拼接得到

$n\le 500,m\le 2n^2$

Solution

我们对于 $0$ 和 $1$ 各建一个矩阵 $f,g$，显然我们有 $f_n=f_{n-1}g_{n-1},g_n=g_{n-1}f_{n-1}$，其中 $f_{n}$ 表示长度为 $2^n$ 的路径的矩阵，对于最长路，我们预处理好 $f$ 和 $g$ 之后枚举二进制枚举答案即可，要从高到低枚举，且每次枚举出 $1$ 后要交换 $f$ 和 $g$

另外由于我们的 $f$ 和 $g$ 只需要存储是否能到达，可以使用 $bitset$ 优化，时间复杂度 $O(\frac{n^3\log v}{w})$

#include <iostream>
#include <bitset>
#define maxn 510
#define maxm 61
#define ll long long
using namespace std;

int n, m;

struct Matrix {
    static const int n = 500;
    bitset<n + 1> a[n + 1];

    Matrix() { clear(); }
    void clear() { for (int i = 1; i <= n; ++i) a[i].reset(); }
    void setone() { for (int i = 1; i <= n; ++i) a[i][i] = 1; }
    bool empty() { for (int i = 1; i <= n; ++i) if (a[i].count() > 0) return false; return true; } 
    friend Matrix operator * (const Matrix &u, const Matrix &v) {
        Matrix w;
        for (int i = 1; i <= n; ++i)
            for (int k = 1; k <= n; ++k)
                if (u.a[i][k]) w.a[i] |= v.a[k];
        return w;
    }
} f[maxm], g[maxm];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z; 
        if (!z) f[0].a[x][y] = 1;
        else g[0].a[x][y] = 1; 
    }
    for (int i = 1; i <= 60; ++i) { 
        f[i] = f[i - 1] * g[i - 1];
        g[i] = g[i - 1] * f[i - 1];
    } ll ans = 0; Matrix s; s.setone();
    for (int i = 60; ~i; --i) {
        if ((s * f[i]).empty()) continue;
        s = s * f[i], swap(f, g), ans |= 1ll << i; 
    } if (ans > 1e18) return cout << -1 << "\n", 0;
    cout << ans << "\n";
    return 0;
}