不理解（WA#5）
查看原帖
不理解（WA#5）
672778
lzy_AC7楼主2023/11/5 16:48

认为以下两种写法一样

而且第一种反而可能出现将负无穷加为正数的情况

但是第一种AC 第二种95

有大佬可以解答一下吗？

写法一：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 52;

inline int read()
{
    int x = 0;bool f = 0;char c  = getchar();
    while(c < '0' || c > '9')f = c=='-',c = getchar();
    while(c >= '0' && c <= '9')x = (x<<1)+(x<<3)+(c^48),c = getchar();
    return f?-x:x;
}

int n,m,T,k,a[N];
inline int id(int t,int x){return (t-1)*n+x;}
struct A
{
    int t,x,y;
}day[201];

struct MT
{
    int n,m;
    ll X[N*5][N*5];
    MT()
    {
        n = m = 0;
        memset(X,0xc0,sizeof X);
        return;
    }
    MT operator * (const MT &x)const
    {
        MT ans;
        ans.n = n,ans.m = x.m;
        for(int i = 1;i <= ans.n;i++)
            for(int k = 1;k <= m;k++)
                //if(X[i][k] != -1)
                    for(int j = 1;j <= ans.m;j++)
                        //if(x.X[k][j]!=-1)
                            ans.X[i][j] = ans.X[i][j] >= X[i][k]+x.X[k][j] ?  ans.X[i][j] : X[i][k]+x.X[k][j];
        return ans;
    }
}t,trans[31];

int main()
{
    n = read(),m = read(),T = read(),k = read();
    for(int i = 1;i <= n;i++)a[i] = read();
    trans[0].n = n*5,trans[0].m = n*5;
    for(int i = 1;i <= m;i++)
    {
        int u,v,w;
        u = read(),v = read(),w = read();
        trans[0].X[id(w,u)][v] = a[v];
    }
    for(int i = n+1;i <= n*5;i++)trans[0].X[i-n][i] = 0;
    for(int i = 1;(1<<i) <= T;i++)trans[i] = trans[i-1]*trans[i-1];

    for(int i = 1;i <= k;i++)day[i].t = read(),day[i].x = read(),day[i].y = read();
    sort(day+1,day+1+k,[](const A x,const A y){return x.t < y.t;});
    day[++k] = {T,0,0};
    t.n = 1,t.m = n*5;
    t.X[1][1] = a[1];

    for(int i = 1;i <= k;i++)
    {
        int res = day[i].t - day[i-1].t;
        for(int j = 0;j <= 30;j++)if((res>>j)&1)t = t*trans[j];
        t.X[1][day[i].x] += day[i].y;
    }
    
    if(t.X[1][1]>0)printf("%lld\n",t.X[1][1]);
    else printf("-1");

    // putchar('\n');
    // system("pause");
    return 0;
}

写法二：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 52;

inline int read()
{
    int x = 0;bool f = 0;char c  = getchar();
    while(c < '0' || c > '9')f = c=='-',c = getchar();
    while(c >= '0' && c <= '9')x = (x<<1)+(x<<3)+(c^48),c = getchar();
    return f?-x:x;
}

int n,m,T,k,a[N];
inline int id(int t,int x){return (t-1)*n+x;}
struct A
{
    int t,x,y;
}day[201];

struct MT
{
    int n,m;
    ll X[N*5][N*5];
    MT()
    {
        n = m = 0;
        memset(X,-1,sizeof X);
        return;
    }
    MT operator * (const MT &x)const
    {
        MT ans;
        ans.n = n,ans.m = x.m;
        for(int i = 1;i <= ans.n;i++)
            for(int k = 1;k <= m;k++)
                if(X[i][k] != -1)
                    for(int j = 1;j <= ans.m;j++)
                        if(x.X[k][j]!=-1)
                            ans.X[i][j] = ans.X[i][j] >= X[i][k]+x.X[k][j] ?  ans.X[i][j] : X[i][k]+x.X[k][j];
        return ans;
    }
}t,trans[31];

int main()
{
    n = read(),m = read(),T = read(),k = read();
    for(int i = 1;i <= n;i++)a[i] = read();
    trans[0].n = n*5,trans[0].m = n*5;
    for(int i = 1;i <= m;i++)
    {
        int u,v,w;
        u = read(),v = read(),w = read();
        trans[0].X[id(w,u)][v] = a[v];
    }
    for(int i = n+1;i <= n*5;i++)trans[0].X[i-n][i] = 0;
    for(int i = 1;(1<<i) <= T;i++)trans[i] = trans[i-1]*trans[i-1];

    for(int i = 1;i <= k;i++)day[i].t = read(),day[i].x = read(),day[i].y = read();
    sort(day+1,day+1+k,[](const A x,const A y){return x.t < y.t;});
    day[++k] = {T,0,0};
    t.n = 1,t.m = n*5;
    t.X[1][1] = a[1];

    for(int i = 1;i <= k;i++)
    {
        int res = day[i].t - day[i-1].t;
        for(int j = 0;j <= 30;j++)if((res>>j)&1)t = t*trans[j];
        t.X[1][day[i].x] += day[i].y;
    }
    
    if(t.X[1][1]>0)printf("%lld\n",t.X[1][1]);
    else printf("-1");

    // putchar('\n');
    // system("pause");
    return 0;
}

#5：

输入：

25 45 52497 185
781 50 344 27 238 816 699 683 322 300 7 708 8016 1933 524 2206 7138 540 2685 18266 189 1585 3401 21085 6529
1 2 5
2 3 5
3 4 2
4 5 4
5 6 4
6 7 3
7 8 4
8 9 5
9 10 3
10 11 3
11 12 3
12 13 1
13 14 5
14 15 2
15 16 1
16 17 2
17 18 1
18 19 4
19 20 1
20 21 4
21 22 2
22 23 4
23 24 4
24 25 3
25 1 5
7 17 4
3 20 5
10 13 2
15 18 3
7 12 2
16 22 4
11 18 5
11 15 1
5 16 2
8 20 1
19 23 2
7 23 5
2 19 5
10 2 3
5 19 2
15 24 3
14 8 5
13 23 3
6 2 5
5 17 5
20860 10 85872
46311 7 43389
34782 8 62574492
33624 6 63163
45217 13 39649
14129 20 21895
13257 5 7779
28588 13 80877
25785 3 23228
29431 4 438101937
45723 3 37367
49610 19 48200
2830 2 68436
3332 2 3326
30652 24 43879
28881 7 63279
5464 14 1688
7784 20 59150
36131 14 50852
31141 20 5601
20352 21 747653147
28290 18 64994
16344 22 54026592
24113 8 68927
27956 11 98573
10756 15 91484
13169 14 78476
18846 8 94092
15655 15 8542
51603 10 556515324
15691 11 93240
2290 5 89857704
32149 20 510353633
12866 11 88387
50189 5 24054
38799 24 51
25973 15 93702
43389 14 39442
44373 25 254546966
48441 6 735857199
52386 3 63326
19172 5 611472555
26266 6 4650
17280 20 25053
35725 10 48122
25105 15 171097615
44163 9 35171
16720 14 62718
45756 12 86476
25047 10 18045
52149 4 50577
9489 21 670958195
7623 14 77059
771 14 61336
41691 22 61958
43500 17 88220
51029 5 38673
13867 22 488833921
19412 22 81618
37541 4 71004
7646 16 323713736
49634 15 84535
34423 5 62791
20870 1 73554
9952 23 32279
22827 18 53437
38234 19 81621
22803 13 55296
50987 8 98897
19584 1 99603
20951 24 602028142
43492 18 9927
44910 25 9317
2205 17 285448251
13207 1 71395
34391 16 500643495
18677 12 26662
17763 3 14069
6676 21 3492
39068 18 56323
43314 20 17700
21695 18 37986
34783 7 37507
42292 12 912337498
8364 18 7728
10811 25 77700
30290 13 89392
3069 11 39438
12386 20 78395
9595 4 78907
25268 7 79773
14703 19 97856
7919 19 31574
47987 17 286402440
37028 6 685968506
16418 2 55441
434 23 210
35270 17 60589
38411 6 87481
37803 16 71009
36069 15 17280
9795 20 99017
19014 20 303835051
3437 22 24691
11040 3 56018
39182 11 886158432
23870 24 24310592
7883 10 87462
11714 3 57047
6198 6 716547568
16745 15 23594
43790 11 69788
15485 23 48289
2537 24 48316
28565 10 93689
4094 14 36438
30202 5 41602
9125 17 3364
1792 1 58175
28071 11 31925
37791 14 28906
40121 10 6666
38421 24 54989
50632 14 616751225
6936 25 31401
19919 18 32910
38127 9 57971
18420 13 3653
33902 21 61234
49752 15 22833
49203 16 838865507
34240 12 835016408
19200 17 43605
25089 10 198468724
21073 24 7981
32744 6 85364
45039 3 47598179
38286 12 618441497
12673 15 73283
21280 1 75290
19893 7 75853
15749 11 96448
45443 17 11989
1298 10 235705099
15207 17 40292
50882 12 78443
51881 3 92181
12995 16 6183
33501 21 64441
46239 20 355318554
16176 10 59412
26366 24 67665
40654 16 34141
51633 13 573710
19880 11 598614786
16227 5 570056808
38876 20 58850
19535 20 40539752
35072 6 40401
33078 14 69358
1342 10 500401111
17368 15 835604042
46676 17 74033
28292 6 579324548
39124 1 98095
15217 18 14420
2802 18 253652692
51783 2 84938
52004 16 46969
51474 23 28552
33807 21 7050
46710 19 32739
40870 12 68840
19302 8 49990
49154 13 768708965
8674 8 4366
51 5 53995
27511 1 75823
41041 2 49494
18799 14 74125
1474 1 87413
16514 14 87140
25848 2 606166157
29480 22 79713
19466 23 16022

输出：

19100096713
2023/11/5 16:48