题解：P8408 [COCI2009-2010#6] GREMLINI

· · 题解

这是一道 dp + 倍增题目。

可以把题目中的关系建为一张有向图，每个点代表一种妖精，边代表 “繁殖” 的关系，边权代表第 i 种妖精从出生到繁殖出第 j 种妖精所需要的最小时间。把这张图的邻接矩阵记为 G.

设 dp_{k, i, j} 为第 i 种妖精产生代数为 k 的第 j 种妖精所需要的最小时间。

那么有：

dp_{k, i, j} = \min _{1 \leq x \leq n}\left\{dp_{k-1, i, x} +G_{x, j}\right\}

定义一种新矩阵乘法，当 A × B = C 时，C_{i, j} = min\left\{A_{i, k} + B_{k, j}\right\}

可以发现，在这种新定义的矩阵乘法中，dp_{k} × G = dp_{k+1}

题目要求 t 年后和祖先关系最远的小妖的代数，也就相当于求一个最大的 k，使 dp_{k} 中至少有一个值小于等于 t。

可以预处理出 F_{x} = dp_{2^x}，之后倍增即可。

Code

#include <bits/stdc++.h>
#define Base 45
#define int long long

using namespace std;

struct matrix
{
    int s;
    int arr[110][110];

    matrix(int num = 100)
    {
        s = num;

        memset(arr, 0x1f, sizeof(arr));
    }

    matrix operator * (const matrix &b) //新定义的矩阵乘法
    {
        matrix c(s);

        for(int i = 1; i <= s; i++)
        {
            for(int j = 1; j <= s; j++)
            {
                for(int k = 1; k <= s; k++)
                {
                    ​​c.arr[i][j] = std::min(c.arr[i][j], arr[i][k] + b.arr[k][j]);
                }
            }
        }

        return c;
    }
};

matrix G[Base + 5], now;

int n, t; 
bool check(matrix x)
{
    int cnt = 0;
    for(int i = 1; i <= x.s; i++)
    {
        for(int j = 1; j <= x.s; j++)
        {
            if(x.arr[i][i] > t)
            {
                cnt++;
            }
        }
    }

    return cnt != x.s * x.s;
}

int g[1010], h[1010];

signed main()
{
    scanf("%lld %lld", &n, &t);

    now.s = n;
    for(int i = 0; i <= Base; i++)
    {
        G[i].s = n;
    }

    for(int i = 1; i <= n; i++)
    {
        int k, y;
        scanf("%lld %lld", &k, &y);

        for(int j = 1; j <= k; j++)
        {
            scanf("%lld", &g[j]);
        }
        for(int j = 1; j <= k; j++)
        {
            scanf("%lld", &h[j]);
        }

        for(int j = 1; j <= k; j++)
        {
            G[1].arr[i][g[j]] = min(G[1].arr[i][g[j]], y + h[j]);
        }
    }

    for(int i = 2; i <= Base; i++) // 预处理
    {
        G[i] = G[i-1] * G[i-1];
    }

    memset(now.arr, 0, sizeof(now.arr));
    int ans = 0, OK = 0;
    for(int i = Base; i >= 1; i--) // 倍增
    {
        matrix _new(n);

        _new = now * G[i];

        if(check(_new) == true)
        {
            OK++;
            ans += (1ll << (i - 1)); // 必须用1ll，不然会爆 long long
            now = _new;
        }
    }
    printf("%lld\n", ans);

    return 0;
}