NOIP 2014 联合权值
程序员文章站
2022-05-22 14:56:10
...
题目链接:
https://www.luogu.org/problemnew/show/P1351
参考洛谷题解:
使用链式前向星储存图。如果使用深度优先搜索的话,是会超时的,如果遍历中间的点,虽然比直接遍历快一点,但是也会超时,画一个有三个顶点一个中心的菊花图,题目就是要求三个顶点两两相乘的和,找规律可得到:结果为三个顶点的和的平方减去三个顶点的平方和,推广到n个顶点也是一样的。由此得出代码:
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int inf=1e6+7;
struct node
{
int from,to,next;
}themap[inf];
int head[inf],thevalue[inf],thenow[inf];
int cnt=0;
int themax=-1,theans=0;
void addedge(int u,int v) //远不如直接在用一个来的好。
{
themap[cnt].from=u;
themap[cnt].to=v;
themap[cnt].next=head[u];
head[u]=cnt++;
themap[cnt].from=v;
themap[cnt].to=u;
themap[cnt].next=head[v];
head[v]=cnt++;
}
int main()
{
int n,u,v;
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d %d",&u,&v);
addedge(u,v);
}
for(int i=1;i<=n;i++)
scanf("%d",&thevalue[i]);
for(int i=1;i<=n;i++)
{
int flag=0;
ll one=-1,two=-1; //最大值和次大值。
ll temp1=0;
ll temp2=0;
for(int j=head[i];j!=-1;j=themap[j].next)
{
//thenow[flag++]=themap[j].to;
int now=themap[j].to; //是其中的值啊.
if(thevalue[now]>one)
{
two=one;
one=thevalue[now];
}
else if(thevalue[now]>two)
two=thevalue[now];
temp1+=thevalue[now];
temp1=temp1%10007;
temp2+=(thevalue[now]*thevalue[now])%10007;
temp2=temp2%10007;
flag++;
}
if(flag==1){}
else
{
if(one*two>themax)
{
themax=one*two;
}
temp1=(temp1*temp1)%10007;
theans+=(temp1-temp2+10007); //防止theans成为负的。
theans=theans%10007;
}
}
printf("%d %d\n",themax,theans%10007);
return 0;
}
上一篇: IE常见BUG总结
下一篇: 大数据存储管理分析:分隔的存储系统