网站首页
编程语言
数据库
系统相关
其他分享
编程问答
CF1630F
2024-08-27
CF1630F-最小割、Dilworth定理
link:https://codeforces.com/contest/1630/problem/F给你一个由\(n\)个顶点组成的无向图,编号从\(1\)到\(n\),其中顶点\(i\)的值为\(a_i\),所有值\(a_i\)都是不同的。如果\(a_u\)整除\(a_v\),则两个顶点\(u\)和\(v\)之间存在一条边。当删除一个顶点时,也就删除了
2024-08-18
题解:CF1630F Making It Bipartite
题意图上有\(n\)个点,且具有点权,点权保证互不相同,若两个点点权有倍数关系,则两点之间有一边,问你最少删去多少个点能使图变为二分图。思路因为如果\(a\)是\(c\)的倍数且\(c\)是\(b\)的个数,所以\(a\)是\(c\)的倍数。由此可以看出,若\(a\)与\(b\)相连且\(b\)与