TsinsenA1221 大楼

题目链接

题意

给出一张带权图, 从 $1$ 结点出发, 问最少走过多少条边, 使得权值总和大于等于 $m$ 。
$1\leq n\leq 100, 1\leq m\leq 10^{18} $

题解

发现给出了一个邻接矩阵,而且从 $i\to k$ 和从 $k\to j$ 的权值和可以更新 $i\to j$ 的最大权值和
可以看做用邻接矩阵中 $g[i][k]+g[k][j]$ 来更新 $g[i][j]$
于是类似于矩乘的做矩阵快速幂棵快速得到走过 $l$ 条边的最大权值

这时不难想到二分,但是再往深层想发现复杂度可能较高,不好卡过这题
于是考虑倍增求答案,使用倍增求出走最多多少条边最大权值会恰好小于 $m$ ,然后加上 $1$ 就是答案

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 107
#define INF 1000000000000000000LL
typedef unsigned long long ll;

template <typename _T> inline void read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while (c < '0' || '9' < c) {
        if (c == '-') y = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
}

void print (ll x) {
    if (x / (ll)10 == 0) putchar(x % (ll)10 + '0');
    else {
        print(x / (ll)10);
        putchar(x % (ll)10 + '0');
    }
}

int N;
ll M;

struct matrix {
    ll a[MAX_N][MAX_N];

    matrix operator * (const matrix b) const {
        matrix ans;
        memset(ans.a, 0, sizeof(ans.a));
        for (int i = 1; i <= N; ++i)
            for (int k = 1; k <= N; ++k)
                if (a[i][k])
                    for (int j = 1; j <= N; ++j)
                        if (b.a[k][j])
                            ans.a[i][j] = std::max(ans.a[i][j], std::min((ll)INF, a[i][k] + b.a[k][j]));
        return ans;
    }
}G, F, H[107];

inline void init () {
    memset(G.a, 0, sizeof(G.a));
}

inline void input () {
    read(N), read(M);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            read(G.a[i][j]);
}

inline bool check (matrix x) {
    for (int i = 1; i <= N; ++i)
        if (x.a[1][i] >= M)
            return true;
    return false;
}

inline void solve () {
    memcpy(H[0].a, G.a, sizeof(H[0].a));
    for (int i = 1; i <= 63; ++i)
        H[i] = H[i - 1] * H[i - 1];
    ll res = 0;
    bool flag = false;
    for (int i = 63; i >= 0; --i) {
        memcpy(F.a, G.a, sizeof(F.a));
        if (!flag)
            memcpy(G.a, H[i].a, sizeof(G.a));
        else
            G = G * H[i];
        if (check(G))
            memcpy(G.a, F.a, sizeof(G.a));
        else {
            flag = true;
            res += ((ll)1 << (ll)i);
        }
    }
    print(res + (ll)1); puts("");
}

int main () {
    int T;
    read(T);
    while (T--) {
        init();
        input();
        solve();
    }
    return 0;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注