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

联合权值题解

程序员文章站 2022-05-22 14:35:08
...

题目

无向连通图 GG 有 n个点,n1条边。点从 1n 依次编号,编号为 i 的点的权值为 Wi ,每条边的长度均为 1。图上两点 (u,v) 的距离定义为 uu 点到 vv 点的最短距离。对于图 G上的点对 (u,v),若它们的距离为 2,则它们之间会产生wu*wv​ 的联合权值。请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?
输入输出格式
输入格式:
第一行包含 1 个整数 n
接下来 n1行,每行包含2 个用空格隔开的正整数u,v,表示编号为 u 和编号为 v 的点之间有边相连。最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i个整数表示图 G 上编号为 i 的点的权值为wi
输出格式:
输出共 1行,包含2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007取余。

输入输出样例
输入样例#1:
5
1 2
2 3
3 4
4 5
1 5 2 3 10
输出样例#1:
20 74

分析

我们来看,因为边权是1,所以我们可枚举点从而进行计算,但这样只有70分,这样我们就要来想一想如何优化,我们分析可发现我们将大部分时间都浪费在找点,所以我们可维护一个数组,表示有多少个点与之相连,这样在枚举点时可以减少一重循环,这样就可以A了
上代码

#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int t,nexty;
    Edge(){t=nexty=0;}
}edge[1000000];
int head[300000]={0},cnt=0;
void add(int a,int b){
    cnt++;
    edge[cnt].t=b,edge[cnt].nexty=head[a];
    head[a]=cnt;
}
long long w[300000]={0};
int main(){
    int n;
    scanf("%d",&n);
    int a,b;
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
    long long sum=0,maxn=0,he,rmax,node;
    for(int i=1;i<=n;i++){
        node=head[i];
        he=(rmax=w[edge[node].t])%10007;
        node=edge[node].nexty;
        for(;node!=0;node=edge[node].nexty){
            sum=(sum+he*w[edge[node].t])%10007;
            maxn=max(maxn,rmax*w[edge[node].t]);
            he=(he+w[edge[node].t])%10007;
            rmax=max(rmax,w[edge[node].t]);
        }
    }
    printf("%lld %lld",maxn,(sum*2)%10007);
    return 0;
}

上一篇: 联合权值

下一篇: 1351 联合权值