- 联合权值
- 2015-06-12 08:50:39 @
我觉得算法应该没有问题,但是只过4个点,是数据范围原因吗?
#include<stdio.h>
#include<string.h>
struct ista
{
int item;
struct ista *next;
};
struct fashion
{
int sonnum;
struct ista *first;
};
struct fashion head[200001];
int dev[200001]={0};
int main( )
{
int i,j,n,a,b;
struct ista *p;
int group=0,alone=0,max1=0,max2=0,sum=0,max=0;
for(i=0;i<=200000;i++)
{
head[i].first=NULL;
head[i].sonnum=0;
}
scanf("%d",&n);
for(i=1;i<=n-1;i++)
{
scanf("%d %d",&a,&b);
p=malloc(sizeof(struct ista));
p->item=a;
p->next=head[b].first;
head[b].first=p;
head[b].sonnum++;
p=malloc(sizeof(struct ista));
p->item=b;
p->next=head[a].first;
head[a].first=p;
head[a].sonnum++;
}
for(i=1;i<=n;i++)
scanf("%d",&dev[i]);
for(i=1;i<=n;i++)
{
if(head[i].sonnum>1)
{
p=head[i].first;
while(p!=NULL)
{
group=group+dev[p->item];
alone=alone+dev[p->item]*dev[p->item];
if(dev[p->item]>max2) max2=dev[p->item];
else if(dev[p->item]>max1) max1=dev[p->item];
p=p->next;
}
sum=(sum-alone+group*group)%10007;
if(max1*max2>max) max=max1*max2;
group=0;alone=0;max1=0;max2=0;
}
}
printf("%d %d",max,sum%10007);
return 0;
}
3 条评论
-
qq872191552 LV 9 @ 2016-11-18 10:51:40
现在看起来过去的代码简直惨不忍睹QAQ
-
2015-06-30 09:49:01@
现在知道了,的确是数据范围问题,改用long long就过了
这个方法的中间计算值太大了
-
2015-06-12 16:47:26@
超时还是什么?
- 1