欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP2014 联合权值

程序员文章站 2022-06-12 13:45:59
...

NOIP2014 联合权值
NOIP2014 联合权值

  • 这道题我拿到是就想到了暴力,先是用vector给每个点加边,然后直接对每个点判断
#include<bits/stdc++.h>
using namespace std;
vector<int> G[200005];
int a[200005],num[200005];
int n,ans,Max;
void Search(int node)
{
    int w=0;
    for(int i=0;i<G[node].size();i++)
        for(int j=0;j<G[node].size();j++)
            if(i!=j){
                int now=a[G[node][i]]*a[G[node][j]];
                Max=max(Max,now);
                w+=now;
            }
    ans+=w;
    return;
}
int main()
{
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
        num[u]++;
        num[v]++;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        if(num[i]>=2) Search(i);
    printf("%d %d",Max,ans);
    return 0;
}
  • 然后我们会想到优化,这时候我们发现我们可以根据一个点与之相连的边数来判断,发现了这样一个规律:当一个点至少有两个点与之相连时才会有权值的出现,根据这一点,我们可以只列举有两个点与之相连的点进行操作
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
bool node[200005];
vector<int> G[200005];
int n,a[200005],Max,Tot;
void Search(int pos,int now,int value){
    node[pos]=1;
    if(now==2){
        int quan=a[pos]*value;
        Max=max(Max,quan);
        Tot+=quan;
        Tot%=10007;
        return;
    }
    for(int i=0;i<G[pos].size();i++){
        if(node[G[pos][i]]==0){
            Search(G[pos][i],now+1,value);
        }
    }
}
int main()
{
//  freopen("link.in","r",stdin);
//  freopen("link.out","w",stdout);
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        memset(node,0,sizeof(node));
        Search(i,0,a[i]);
    }
    printf("%d %d",Max,Tot);
    return 0;
}
  • 但是这样依然不能过,我们可以进一步优化,因为每个点都会计算与之相连的点的乘积,这是就用上了乘法的神奇预算(其实我也不知道怎么化简的),然后最大值求的时候我们可以先排个序,然后只判断前两个的值即可,下面是满分代码:
#include<bits/stdc++.h>
using namespace std;
int n,d[200010],Max=0,sum=0;
vector<int> G[200010];
bool cmp(int a,int b){
    return d[a]>d[b];
}
int main(){
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&d[i]);
    for(int i=1;i<=n;++i){
        if(G[i].size()<2) continue;
        sort(G[i].begin(),G[i].end(),cmp);
        Max=max(Max,d[G[i][0]]*d[G[i][1]]);
        int s=0;
        for(int j=0;j<G[i].size();++j)
            s+=d[G[i][j]];
        for(int j=0;j<G[i].size();++j)
            sum=((1ll*(s-d[G[i][j]]+10007)*d[G[i][j]])%10007+sum)%10007;
    }
    printf("%d %d\n",Max,sum);
}
相关标签: NOIP