复赛1:假期计划

P8817

我们考虑一条 1−abcd−1 的路径,n4 的枚举,暴力方法只得一部分分数,

直接贪心不行,a选权值大的,a的下一个选择b可能很小。

先预处理出对每个点 i ,同时满足到 i 和到 1 号点距离不超过 k+1 的点中权值前三大的点。为什么是前三大?因为接下来要枚举中间两个点 B,C ,然后 A 从 B 预处理的前三大点中选,D 从 C 预处理的前三大点中选,为了避免 A 和 C,D 重复以及 D 和 A,B 重复。

暴力代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**************************************************************** 
 * Description: 2022提高组复赛第一题,假期计划
 * Author: Alex Li
 * Date: 2023-10-02 19:39:50
 * LastEditTime: 2023-10-05 11:03:09
****************************************************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long LL;
const int N=2505;

int n,m,k;
LL a[N]; // 结点的权值,范围是10^18次方,所以需要LL型
vector<int> G[N];//有n个结点m条边, n最大取250,用动态数组存图
int d[N][N];//各点之间的距离,k是条件
int b[N][3];//某点前三大的权值结点

void bfs(int s){  // 求出各点到s点的距离
    for(int i=1;i<=n;i++)d[s][i]=-1;
    queue<int> q;
    q.push(s),d[s][s]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        if(d[s][u]==k)break;
        for (auto v:G[u]){
        if(d[s][v]==-1)d[s][v]=d[s][u]+1,q.push(v);    
        }
    }
}


 int main(){
    cin>>n>>m>>k;
    k++;
    for (int i =2; i <=n; i++){
        cin>>a[i];
    }
    while(m--){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(1);
    for (int i =2; i <=n; i++){
        bfs(i);//宽搜出每个i点与其它结点的权值
        int &x1=b[i][0],&x2=b[i][1],&x3=b[i][2];
        for (int j = 2; j <=n; j++){
            if(i==j)continue;
            if(d[1][j]!=-1&&d[i][j]!=-1){//选出每个结点前三大权值的结点(不超过K+1)
                if(a[j]>a[x1]){
                    x3=x2,x2=x1,x1=j;
                }else if(a[j]>a[x2]){
                    x3=x2,x2=j;
                }else if(a[j]>a[x3]){
                    x3=j;
                }
            }
        }
        
    }
    LL ans=0;
    //遍历B、C,然后在B、C后再遍历A、D,只是A、D是在B、C权值最大的三个点里面。所以遍历范围小了。
    for (int i =2; i <=n; i++){
        for (int j = i+1; j <=n; j++){
            if(d[i][j]==-1)continue;
            for (int k1 =0; k1 <3; k1++){
                for (int k2 = 0; k2< 3; k2++){
                    int x=b[i][k1],y=b[j][k2];
                    if(x==0||y==0||x==y||x==i||x==j||y==i||y==j)continue;
                    ans=max(ans,a[i]+a[j]+a[x]+a[y]);
                }
                
            }
            
        }
        
    }
    
cout<<ans;
return 0;

 }

满分:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**************************************************************** 
 * Description: 2022提高组复赛第一题,假期计划
 * Author: Alex Li
 * Date: 2023-10-02 19:39:50
 * LastEditTime: 2023-10-05 11:03:09
****************************************************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long LL;
const int N=2505;

int n,m,k;
LL a[N]; // 结点的权值,范围是10^18次方,所以需要LL型
vector<int> G[N];//有n个结点m条边, n最大取250,用动态数组存图
int d[N][N];//各点之间的距离,k是条件
int b[N][3];//某点前三大的权值结点

void bfs(int s){  // 求出各点到s点的距离
    for(int i=1;i<=n;i++)d[s][i]=-1;
    queue<int> q;
    q.push(s),d[s][s]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        if(d[s][u]==k)break;
        for (auto v:G[u]){
        if(d[s][v]==-1)d[s][v]=d[s][u]+1,q.push(v);    
        }
    }
}


 int main(){
    cin>>n>>m>>k;
    k++;
    for (int i =2; i <=n; i++){
        cin>>a[i];
    }
    while(m--){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(1);
    for (int i =2; i <=n; i++){
        bfs(i);//宽搜出每个i点与其它结点的权值
        int &x1=b[i][0],&x2=b[i][1],&x3=b[i][2];
        for (int j = 2; j <=n; j++){
            if(i==j)continue;
            if(d[1][j]!=-1&&d[i][j]!=-1){//选出每个结点前三大权值的结点(不超过K+1)
                if(a[j]>a[x1]){
                    x3=x2,x2=x1,x1=j;
                }else if(a[j]>a[x2]){
                    x3=x2,x2=j;
                }else if(a[j]>a[x3]){
                    x3=j;
                }
            }
        }
        
    }
    LL ans=0;
    //遍历B、C,然后在B、C后再遍历A、D,只是A、D是在B、C权值最大的三个点里面。所以遍历范围小了。
    for (int i =2; i <=n; i++){
        for (int j = i+1; j <=n; j++){
            if(d[i][j]==-1)continue;
            for (int k1 =0; k1 <3; k1++){
                for (int k2 = 0; k2< 3; k2++){
                    int x=b[i][k1],y=b[j][k2];
                    if(x==0||y==0||x==y||x==i||x==j||y==i||y==j)continue;
                    ans=max(ans,a[i]+a[j]+a[x]+a[y]);
                }
                
            }
            
        }
        
    }
    
cout<<ans;
return 0;

 }
Scroll to Top