2018-Sp27-lyk/E

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL INF = 1E18;
void print(LL x){
    printf(x < 0 ? "  -INF" : "%6lld", x);
}

#define maxn 129
bool g[maxn][maxn];
LL w[maxn];
LL n, m, t, T;

struct matrix{
    LL d[maxn][maxn];
    matrix(){
        //初始化power(0) 
        for(int i = 0; i <= 2 * n; i += 1)
            for(int j = 0; j <= 2 * n; j += 1)
                d[i][j] = i == j ? 0 : -INF;
        for(int i = 0; i < n; i += 1)
            for(int j = 0; j < n; j += 1)
                d[j + n][i] = 0;
    }
    matrix operator * (const matrix & b){
        //矩阵乘法 
        matrix res;
        for(int k = 0; k <= 2 * n; k += 1)
            for(int i = 0; i <= 2 * n; i += 1)
                for(int j = 0; j <= 2 * n; j += 1)
                    res.d[i][j] = max(res.d[i][j], d[i][k] + b.d[k][j]);
        return res;
    }
    void out(int n){
        for(int i = 0; i < n; i += 1){
            for(int j = 0; j < n; j += 1) print(d[i][j]);
            printf("\n");
        }
        printf("\n");
    }
}one; 

matrix power(LL r){
    //矩阵快速幂 
    //power(r).d[i][j]表示从点i到点j(但没有走到j)至多r步点权值最大和
    //需要额外标号为2*n的点
    //power(r).d[i][2*n],表示从点i到某个点至多r步点权值最大和
    matrix res, a = one;
    for(; r; r >>= 1, a = a * a) if(r & 1) res = res * a;
    return res;
}
int main(){
    scanf("%lld %lld %lld %lld", &n, &m, &t, &T);
    for(int i = 0; i < m; i += 1){
        int u, v;
        scanf("%d %d", &u, &v);
        g[u - 1][v - 1] = true;
    }
    for(int i = 0; i < n; i += 1){
        scanf("%lld", w + i);
        w[i + n] = w[i];
    }
    //初始化power(1) 
    for(int i = 0; i < n; i += 1)
        for(int j = 0; j < n; j += 1){
            if(i != j) one.d[i][j] = one.d[i + n][j + n] = -INF;
            if(g[i][j]) one.d[i][j] = one.d[i + n][j + n] = w[i]; 
        }
    for(int i = 0; i < n; i += 1)
        for(int j = 0; j < n; j += 1){
            one.d[i][j + n] = -INF;
            one.d[i + n][j] = w[i];
        }
    for(int i = 0; i < 2 * n; i += 1){
        one.d[i][2 * n] = w[i];
        one.d[2 * n][i] = -INF;
    }

    matrix db = power(T);
    matrix sg = power(t - T);
    LL ans = -INF;
    for(int i = 0; i < n; i += 1)
        for(int j = 0; j < n; j += 1){
            ans = max(ans, db.d[i][j] * 2 + sg.d[j + n][i]);
            //需要考虑翻倍后不再走的情况 
            ans = max(ans, db.d[i][2 * n] * 2 + sg.d[j][i]);
        }
    printf("%lld\n", ans);
}
}}}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1E18;
void print(LL x){
    printf(x < 0 ? "  -INF" : "%6lld", x);
}
#define maxn 129
bool g[maxn][maxn];
LL w[maxn];
LL n, m, t, T;
struct matrix{
    LL d[maxn][maxn];
    matrix(){
        //初始化power(0) 
        for(int i = 0; i <= 2 * n; i += 1)
            for(int j = 0; j <= 2 * n; j += 1)
                d[i][j] = i == j ? 0 : -INF;
        for(int i = 0; i < n; i += 1)
            for(int j = 0; j < n; j += 1)
                d[j + n][i] = 0;
    }
    matrix operator * (const matrix & b){
        //矩阵乘法 
        matrix res;
        for(int k = 0; k <= 2 * n; k += 1)
            for(int i = 0; i <= 2 * n; i += 1)
                for(int j = 0; j <= 2 * n; j += 1)
                    res.d[i][j] = max(res.d[i][j], d[i][k] + b.d[k][j]);
        return res;
    }
    void out(int n){
        for(int i = 0; i < n; i += 1){
            for(int j = 0; j < n; j += 1) print(d[i][j]);
            printf("\n");
        }
        printf("\n");
    }
}one; 
matrix power(LL r){
    //矩阵快速幂 
    //power(r).d[i][j]表示从点i到点j(但没有走到j)至多r步点权值最大和
    //需要额外标号为2*n的点
    //power(r).d[i][2*n],表示从点i到某个点至多r步点权值最大和
    matrix res, a = one;
    for(; r; r >>= 1, a = a * a) if(r & 1) res = res * a;
    return res;
}
int main(){
    scanf("%lld %lld %lld %lld", &n, &m, &t, &T);
    for(int i = 0; i < m; i += 1){
        int u, v;
        scanf("%d %d", &u, &v);
        g[u - 1][v - 1] = true;
    }
    for(int i = 0; i < n; i += 1){
        scanf("%lld", w + i);
        w[i + n] = w[i];
    }
    //初始化power(1) 
    for(int i = 0; i < n; i += 1)
        for(int j = 0; j < n; j += 1){
            if(i != j) one.d[i][j] = one.d[i + n][j + n] = -INF;
            if(g[i][j]) one.d[i][j] = one.d[i + n][j + n] = w[i]; 
        }
    for(int i = 0; i < n; i += 1)
        for(int j = 0; j < n; j += 1){
            one.d[i][j + n] = -INF;
            one.d[i + n][j] = w[i];
        }
    for(int i = 0; i < 2 * n; i += 1){
        one.d[i][2 * n] = w[i];
        one.d[2 * n][i] = -INF;
    }
    matrix db = power(T);
    matrix sg = power(t - T);
    LL ans = -INF;
    for(int i = 0; i < n; i += 1)
        for(int j = 0; j < n; j += 1){
            ans = max(ans, db.d[i][j] * 2 + sg.d[j + n][i]);
            //需要考虑翻倍后不再走的情况 
            ans = max(ans, db.d[i][2 * n] * 2 + sg.d[j][i]);
        }
    printf("%lld\n", ans);
}