NOIP 2014 联合权值

题目链接：

https://www.luogu.org/problemnew/show/P1351

参考洛谷题解：

使用链式前向星储存图。如果使用深度优先搜索的话，是会超时的，如果遍历中间的点，虽然比直接遍历快一点，但是也会超时，画一个有三个顶点一个中心的菊花图，题目就是要求三个顶点两两相乘的和，找规律可得到：结果为三个顶点的和的平方减去三个顶点的平方和，推广到n个顶点也是一样的。由此得出代码：

#include       
#include 
#include 
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;ione){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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！