E - Another Postman Problem FZU - 2038

E - Another Postman Problem FZU - 2038

题意：

n个点通过n-1个边两两相连，每个边有权值，求对于每个点到其他点的距离和的总和

题解：

我们以下图中的1-2这条边为例子，1-2这条边一共计算了几次？
我们现在将这个图当作一个树，（题目说了n个点，n-1个边，所以完全可以），0为根节点，1-2这条边的右侧有2个点，左侧有4个点，两两配对，所以经过了2 *4 * 2(最后乘2是因为顺序可以颠倒，比如1到2，2到1)
而1-2边的右侧就是2的子树大小，所以我们就看将一个边的计算数 = sonsiz（子树大小） * （n-sonsiz） * 2 * w(权值)

代码：

#include<stdio.h> #include<string.h> #include<vector> using namespace std; #define ll __int64 struct zuobiao {int v,w; }now; ll ans; int vis[100010],n; vector<zuobiao >mp[100010]; ll dfs(int u) {vis[u]=1;ll sonsiz=1;ll tmp;for(int i=0;i<mp[u].size();i++){int v=mp[u][i].v;if(vis[v]==0){tmp=dfs(v);ans+=2*mp[u][i].w*tmp*(n-tmp);sonsiz+=tmp;}}return sonsiz; } int main() {int t;int kase=0;scanf("%d",&t);while(t--){memset(vis,0,sizeof(vis));scanf("%d",&n);for(int i=0;i<n;i++){mp[i].clear();}for(int i=0;i<n-1;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);now.v=v;now.w=w;mp[u].push_back(now);now.v=u;now.w=w;mp[v].push_back(now);}ans=0;dfs(0);printf("Case %d: %I64d\n",++kase,ans);} }

总结

以上是生活随笔为你收集整理的E - Another Postman Problem FZU - 2038的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。