UVA1104 芯片难题 Chips Challenge
答案最多不会超过160,可以考虑枚举答案。
当我们枚举答案并且确定每行的最大限度maxn时,其实是可以放多于答案个芯片的。因为此时仍然合法,只是不优秀。
现在,我们考虑第i行/列有ti个部件,那么我们知道0≤ti≤maxn同时,
ti=ai,1+ai,2+⋯+ai,nti=a1,i+a2,i+⋯+an,i移个项,发现又是流量平衡的形式了。
所以我们考虑建立Ai表示第i行/列的第一个等式,Bi表示第二个。那么可以从Bi→Ai连费用为 1 ,上界为maxn的边。
然后考虑对于ai,j的确定。如果它已经确定是 部件 了,那么从Ai→Bj连费用为 0 上下界均为 1 的边,如果确定不是,上下界都是 0 ,如果不确定,上界为 1 下界为 0 。
最后跑最大费用上下界可行流就好了。
关于各种流,这篇 Blog 感觉写的很好,安利一下。
但是写了很久发现上下界可行流挂掉了。。因为这题有环啊。。。
翻了翻题解,发现了一个很优秀的做法。首先建立两排点,分别表示第i行和第i列。然后从i行到i列连一个容量为 inf 的边,费用为 0 。然后从原点向第i行连容量为 lim 的边,费用为0,从第i列向汇点连容量为 lim 的边,费用也是 0 。这样我们从一开始就可以跑满流了。现在中间两个点之间的流量,其实是maxn−ti。
然后考虑会出现C和.,首先如果出现了 . ,那么我们从第i行向第j列连一条容量为 1 费用为 1 的边。但是如果这里是C怎么办?按照原本的想法我们应当去连一条最小限度为 1 最大限度也是 1 的边。但是我们可以避免这样做,我们可以连一条容量为 1 ,费用为 1 + F 的边,其中 F 是一个极大值,是所有 1 的费用加起来也达不到的。这样的好处在于,我们会尽量满足C的点,并且还可以数出来满足了多少个C的点,如果数量不足则是无解。
cpp
1 |
|