P3128 [USACO15DEC]最大流Max Flow

    • 616通过
    • 1.2K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 最近公共祖先,LCA 树链剖分,树剖 USACO 2015 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John has installed a new system of $N-1$ pipes to transport milk between the $N$ stalls in his barn ($2 \leq N \leq 50,000$ ), conveniently numbered $1 \ldots N$ . Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

    FJ is pumping milk between $K$ pairs of stalls ($1 \leq K \leq 100,000$ ). For the $i$ th such pair, you are told two stalls $s_i$ and $t_i$ , endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from $s_i$ to $t_i$ , then it counts as being pumped through the endpoint stalls $s_i$ and

    $t_i$ , as well as through every stall along the path between them.

    FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道,隔间编号从1到N。所有隔间都被管道连通了。

    FJ有K(1≤K≤100,000)条运输牛奶的路线,第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力,你需要计算压力最大的隔间的压力是多少。

    输入输出格式

    输入格式:

    The first line of the input contains $N$ and $K$ .

    The next $N-1$ lines each contain two integers $x$ and $y$ ($x \ne y$ ) describing a pipe

    between stalls $x$ and $y$ .

    The next $K$ lines each contain two integers $s$ and $t$ describing the endpoint

    stalls of a path through which milk is being pumped.

    输出格式:

    An integer specifying the maximum amount of milk pumped through any stall in the

    barn.

    输入输出样例

    输入样例#1: 复制
    5 10
    3 4
    1 5
    4 2
    5 4
    5 4
    5 4
    3 5
    4 3
    4 3
    1 3
    3 5
    5 4
    1 5
    3 4
    输出样例#1: 复制
    9
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。