Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「BZOJ 3275」Number - 最小割

    N N 个正整数,需要从中选出一些数,使这些数的和最大。

    若两个数 a, b a,\ b 同时满足以下条件,则 a, b a,\ b 不能同时被选。

    1. 存在正整数 c c ,使 a2+b2=c2 a ^ 2 + b ^ 2 = c ^ 2
    2. gcd(a, b)=1 \gcd(a,\ b) = 1

    于  BZOJ, Dinic, 二分图染色, 最小割, 网络流 继续阅读

  2. 「NOIP2010」关押罪犯 - 二分图染色

    S 城现有两座监狱,一共关押着 N 名罪犯,编号分别为 1 ~ N,我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。每年每一对有仇恨的罪犯会发生一次冲突。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力。那么,应如何分配罪犯,才能使 Z 市长看到的那个冲突事件的影响力最小,求这个最小值是多少?

    于  CodeVS, NOIP, Vijos, 二分图染色, 二分答案, 图论, 洛谷 继续阅读