70->0
查看原帖
70->0
444707
Alphys楼主2022/11/8 13:24

救救孩子

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 3000;
const int inf = 0x3f3f3f3f;
int dist[MAXN][MAXN],n,m,k;
LL val[MAXN],maxn[MAXN][MAXN][4],ans,wh[MAXN][MAXN][4];
vector<int> g[MAXN],lesk[MAXN];
queue<int> q;
void bfs(int s){
    q.push(s);
    dist[s][s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            if(dist[s][v]!=inf)continue;
            dist[s][v]=dist[s][u]+1;
            if(dist[s][v]<=k)lesk[s].push_back(v);          
            q.push(v);
        }
    }
}
void floyd(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int l=0;l<=3;l++)
            maxn[i][j][l]=-inf;
    for(int u=1;u<=n;u++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][u]<=k&&dist[u][j]<=k&&u!=i&&u!=j&&i!=j){
                    for(int l=0;l<=3;l++){
                        if(val[u]>maxn[i][j][l]){
                            for(int p=3;p>=l;p--){
                                maxn[i][j][p]=maxn[i][j][p-1];
                                wh[i][j][p]=wh[i][j][p-1];
                            }
                            maxn[i][j][l]=val[u];
                            wh[i][j][l]=u;
                        }
                    }
                }
}
int main(){
    freopen("holiday.in","r",stdin);
    freopen("holiday.out","w",stdout);
    scanf("%d%d%d", &n, &m, &k);
    k++;
    for(int i=2;i<=n;i++)scanf("%lld", val+i);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(dist,0x3f,sizeof(dist));
    for(int i=1;i<=n;i++)bfs(i);
    floyd();
    for(int i:lesk[1]){
        if(i==1)continue;
        for(int j:lesk[1]){
            if(i==j||j==1||dist[i][j]>2*k)continue;
            for(int u:lesk[i]){
                if(u==i||u==1||dist[j][u]>2*k||u==j)continue;
                for(int l=0;l<=3;l++){
                    if(i==wh[j][u][l]||j==wh[j][u][l]||u==wh[j][u][l]||wh[j][u][l]==1)continue;
                    ans=max(ans,val[i]+val[j]+val[u]+maxn[j][u][l]);
                    break;
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

洛谷官方数据70pts,但CCF评测爆零。

是因为评测环境的问题导致CE吗?GD考试时用的是windows系统,但我用考场的NOI Linux虚拟机中的Code::blocks编译没有报错。

求各位dalao帮忙看看代码是否有误

如果没有问题,申诉有希望挽救吗

2022/11/8 13:24
加载中...