2019-team154-001

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(Scoreboard.png,500px)]]
== 概述 ==

七月集训第一场

== 流水账 ==
=== dafu456 ===
三人第一次组队打比赛。（合作愉快）


=== I ===
题意：给定一个带权图，图上有n个点，点上有人，和s（s≤10）个隐藏处，每个隐藏处有一个容量上限，让n个点上的所有人，都跑到隐藏处中。最短时间记作最后一个人跑到隐藏点的最短时间。问最短时间。

题解：二分答案。注意到隐藏点数量很少，先对于每个隐藏点跑一遍最短路。再根据n个点到隐藏点的最短路是否在mid之内来连边，建立网络流模型。这样点可能会很多。注意到n个点对于隐藏点的连接情况最多有（1 << s）种，不是很多。因此把情况相同的点缩成一个点，人数记为这些点的人数之和。源点向（1<<s）种情况连边，容量为人数；情况向隐藏点（如果满足最短路小于二分的答案的话）连边，容量无限；隐藏点向汇点连边，容量即为容量。跑网络流就好。

PS：#define int long long大法好


=== K ===
题意：加入最少的边使得树中无桥，输出方案。

结论：每个度为1节点都要连边，连接 i 和 i + 叶子节点个数的上取整可以保证不存在只在一颗子树内连边的情况。

注意：是连接 i 与 i + 叶子节点的上取整而不是下去整（题解pdf的bug）

概述

七月集训第一场

流水账

dafu456

三人第一次组队打比赛。（合作愉快）

I

题意：给定一个带权图，图上有n个点，点上有人，和s（s≤10）个隐藏处，每个隐藏处有一个容量上限，让n个点上的所有人，都跑到隐藏处中。最短时间记作最后一个人跑到隐藏点的最短时间。问最短时间。

题解：二分答案。注意到隐藏点数量很少，先对于每个隐藏点跑一遍最短路。再根据n个点到隐藏点的最短路是否在mid之内来连边，建立网络流模型。这样点可能会很多。注意到n个点对于隐藏点的连接情况最多有（1 << s）种，不是很多。因此把情况相同的点缩成一个点，人数记为这些点的人数之和。源点向（1<

PS：#define int long long大法好

K

题意：加入最少的边使得树中无桥，输出方案。

结论：每个度为1节点都要连边，连接 i 和 i + 叶子节点个数的上取整可以保证不存在只在一颗子树内连边的情况。

注意：是连接 i 与 i + 叶子节点的上取整而不是下去整（题解pdf的bug）

附加文件