文档章节

2018牛客多校第六场 G.Pikachu

o
 osc_4nmshwhm
发布于 2018/08/07 01:06
字数 512
阅读 19
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题意:

  给出一棵n个点的树,每条边有边权。对这个树加边变成一个完全图。新加的边的权值为边上两点在树上的距离。求完全图上任意两点的最大流之和。

题解:

  一共有C(n,2)个点对。假设当前求s到t之间的最大流,也就是最小割。那么割完之后会是2个连通块,且连通块内部是完全图。

  因为是最小割,所以被割掉的边权和最小。即两个连通块内部的边权和最大。那么就会有一个连通块是孤立点,取s和t中到其余所有点距离小的作为孤立点。

  问题变成了求每个点到其他所有点的距离。

  dfs第一次求每个点到他所有儿子节点的距离,dfs第二次将剩余的距离更新。

  最后排序统计答案。答案会爆ll所以要用类似大数的方法处理一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const ll inf = 1e17;
int t, n, tot, cnt;
int u, v;
int num[N];
int head[N], to[N<<1], nxt[N<<1], w[N<<1];
ll ans;
ll d[N];
void dfs(int u, int fa) {
    num[u] = 1;
    d[u] = 0;
    for(int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        dfs(v, u);
        num[u] += num[v];
        d[u] += d[v]+num[v]*w[i];
    }
}
void re_dfs(int u, int fa) {
    for(int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        d[v] = d[u]+(n-2*num[v])*w[i];
        re_dfs(v, u);
    }
}
int main() {
    scanf("%d", &t);
    for(int casee = 1; casee <= t; casee++) {
        scanf("%d", &n);
        tot = ans = cnt = 0;
        memset(head, -1, sizeof(int)*(n+2));
        for(int i = 1; i < n; i++) {
            scanf("%d%d", &u, &v);
            to[++tot] = v; nxt[tot] = head[u]; head[u] = tot; scanf("%d", &w[tot]);
            to[++tot] = u; nxt[tot] = head[v]; head[v] = tot; w[tot] = w[tot-1];
        }
        dfs(1, 0);
        re_dfs(1, 0);
        sort(d+1, d+n+1);
        for(int i = 1; i <= n; i++) {
            ans += d[i]*(n-i);
            cnt += ans/inf;
            ans %= inf;
        }
        if(cnt) printf("Case #%d: %d%017lld\n", casee, cnt, ans);
        else printf("Case #%d: %lld\n", casee, ans);
    }
} 
View Code

 

 

  

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

如果你失明了,你怎么编程? - How can you program if you're blind?

问题: Sight is one of the senses most programmers take for granted. 视觉是大多数程序员认为理所当然的感官之一。 Most programmers would spend hours looking at a computer monitor......

技术盛宴
50分钟前
16
0
如何删除使用Python的easy_install安装的软件包? - How do I remove packages installed with Python's easy_install?

问题: Python's easy_install makes installing new packages extremely convenient. Python的easy_install使安装新包非常方便。 However, as far as I can tell, it doesn't implement th......

fyin1314
今天
11
0
如何将逗号分隔的字符串转换为数组? - How to convert a comma separated string to an array?

问题: I have a comma separated string that I want to convert into an array, so I can loop through it. 我有一个逗号分隔的字符串,我想将其转换成数组,因此可以循环遍历它。 Is the...

富含淀粉
今天
13
0
深源恒际:担心个人身份被冒用?不存在!

本文作者:c****t 近日,苟晶被冒名顶替身份参加高考的事件在社会各界掀起广泛热议。事件调查结果公布后,舆论风向逆转,吃瓜群众认为当事人夸大其词消费了公众情绪,一边对当事人所遭遇的不...

百度开发者中心
昨天
5
0
CKEditor 5 + SpringBoot实战(三):SpringData JPA数据持久化

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部