做选择的网站,网站数据库文件名,企业如何注册网站,wordpress 文章版本[Luogu 1351] NOIP2014 联合权值 存图#xff0c;对于每一个点 \(u\)#xff0c;遍历它的所有邻接点。以 \(u\) 为中转点的点对中#xff0c;\((x,y)\) 的联合权值 \(w_x \cdot w_y\) 最大#xff0c;当且仅当 \(x\) 与 \(y\) 的点权在 \(u\) 的所有邻接点中是前两大的。 成…[Luogu 1351] NOIP2014 联合权值 存图对于每一个点 \(u\)遍历它的所有邻接点。以 \(u\) 为中转点的点对中\((x,y)\) 的联合权值 \(w_x \cdot w_y\) 最大当且仅当 \(x\) 与 \(y\) 的点权在 \(u\) 的所有邻接点中是前两大的。 成功尝试内嵌 HTML 控制背景色开心。 每遍历一个点 \(v\)它对联合权值之和 \(\mathrm{sum}\) 的贡献等于其点权 \(w_v\) 乘目前已遍历点的点权和 \(\mathrm{NodeSum}\) 再乘 \(2\)即 \(\mathrm{sum} 2w_v \cdot \mathrm{NodeSum}\)。取模省略代码中体现 然后一边求 \(u\) 的邻接点中的最大点权 \(\mathrm{max1}\) 和次大点权 \(\mathrm{max2}\)一边更新 \(\mathrm{NodeSum}\)教练跟我说更新这个的过程叫什么前序和优化。 \(u\) 的邻接点遍历完毕后\(\mathrm{sum}\) 也更新完毕了。至于最大联合权值 \(\mathrm{ans}\)比较当前 \(\mathrm{ans}\) 与此次遍历求出的 \(\mathrm{max1} \cdot \mathrm{max2}\)更新最大值即可。 最终输出 \(\mathrm{ans}\) 与 \(\mathrm{sum}\) 即可。 #include algorithm
#include cstdio
using std::max;
const int MAXN2000010,P10007;
int n,ans,sum,w[MAXN];
struct Edge
{int to;Edge *next;Edge(int to,Edge* next):to(to),next(next){}~Edge(void){if(next!nullptr)delete next;}
}*head[MAXN];
void Initialize(void)
{for(int i1;in;i)head[i]nullptr;
}
void AddEdges(int u,int v)
{head[u]new Edge(v,head[u]);head[v]new Edge(u,head[v]);
}
void Solve(int u)
{int NodeSum0,max10,max20;for(Edge *ihead[u];i!nullptr;ii-next){int vi-to;sum(sum(NodeSum*w[v]1))%P;if(max1w[v]){max2max1;max1w[v];}elsemax2max(max2,w[v]);NodeSum(NodeSumw[v])%P;}ansmax(ans,max1*max2);
}
void Destroy(void)
{for(int i1;in;i)delete head[i];
}
int main(int argc,char** argv)
{scanf(%d,n);for(int i1,u,v;in;i){scanf(%d %d,u,v);AddEdges(u,v);}for(int i1;in;i)scanf(%d,w[i]);for(int i1;in;i)Solve(i);printf(%d %d\n,ans,sum);return 0;
} 谢谢阅读。 转载于:https://www.cnblogs.com/Capella/p/9135482.html
