青烟绕指柔 level
获赞
26
粉丝
34
关注
8
看过 TA
5
中央美术学院
2022
算法工程师
IP属地：四川
暂未填写个人简介
私信
关注
发布(383) 评论 刷题
2019-12-27 12:12
中央美术学院 算法工程师
最小割树(Gomory-Hu Tree)
最小割树的定义： 定义一棵树T为最小割树，如果对于树上的所有边(s,t)，树上去掉(s,t)后产生的两个集合恰好是原图上(s,t)的最小割把原图分成的两个集合，且边(u,v)的权值等于原图上(u,v)的最小割。 最小割树的性质：原图上u,v两点最小割就是最小割树上u到v的路径上权值最小的边。 我们要知道，最小割树是对于无向图来说的，有向图不存在此树及性质。 我们可以利用 分治的思想去构造最小割树 ，每次随机选两个点，对此两点跑最小割，之后在最小割树上连边。 然后对于跑完之后的残量网络，上面的点集分成了两个集合，然后分别分治下去即可。（最后一次bfs，达不到终点，即增广数组有些点的值为...
0 点赞 评论 收藏
分享
2019-12-27 12:11
已编辑
中央美术学院 算法工程师
[CQOI2016]不同的最小割
题目描述 学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 s,ts,t 不在同一个部分中，则称这个划分是关于 s,ts,t 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 s,ts,t 的最小割指的是在关于 s,ts,t 的割中容量最小的割。 而对冲刺 NOI 竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽，考虑有 NN 个点的无向连通图中所有点对的最小割的容量，共能得到 N(N-1)/2N(N−1)/2 个数值。这些数值中互不相同的有多少个呢？这似乎是个有趣的问...
0 点赞 评论 收藏
分享
2019-12-27 12:11
中央美术学院 算法工程师
[ZJOI2011]最小割
题目描述 小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： ”对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。 对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割“ 现给定一张无向图，小白有若干个形如”图中有多少对点它们的最小割的容量不超过x呢“的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。 输入格式 输入文件第一行有且只有一个正整数T，表示测试数据...
0 点赞 评论 收藏
分享
关注他的用户也关注了：
牛客网
牛客企业服务