for (int i = 0; i < n; i ++ )
for (int j = 0; j < i; j ++ )
{
auto a = w[i], b = w[j];
if (is_overlap(a.s, a.s + a.d, b.s, b.s + b.d)) add(i, j + n), add(j, i + n);
if (is_overlap(a.s, a.s + a.d, b.t - b.d, b.t)) add(i, j), add(j + n, i + n);
if (is_overlap(a.t - a.d, a.t, b.s, b.s + b.d)) add(i + n, j + n), add(j, i);
if (is_overlap(a.t - a.d, a.t, b.t - b.d, b.t)) add(i + n, j), add(j + n, i);
}
为什么a的开始 与 b的开始重合了, 就要a的开始和b的末尾连,, b的开始和a的末尾连?
第二次也正着连,,虽然可能会和第四次重边,,但是逻辑也说得过去啊,,
11 走不通 可以走 12
22 走不通 也可以走 12啊
为什么它建图走的是2 到1 呢,,,
解
当成2-sat问题来做就已经把每个数必定从0 1中选一个出来, a的0和b的1不相容 则必有a的0 和b的1 同时存在
更进一步,你已经抽象成2-sat问题了,,原问题的用生活常识去解释,多少会造成点难题理解
把 两个婚礼的冲突 解释成 !(a&b) 整体为1 较好,然后 把全部的运算符号变成 蕴含表达符,也是那个“推出”符号 只有这个符号才能建图,,模板题里能建图的也全都是这个符号,,
而且这些 ~ | & 都能变成 蕴含表达符,,~离散数学里学过~,
本题的化简过程:
!(a&b) = 非a | 非b = a 推出 非b
!(a&b) = 非b | 非a = b 推出 非a
至此 我们知道了为何第二条边会反着键,,
还有第二个问题?
for (int i = 0; i < n; i ++ )
for (int j = 0; j < i; j ++ )
{
auto a = w[i], b = w[j];
if (is_overlap(a.s, a.s + a.d, b.s, b.s + b.d)) add(i, j + n), add(j, i + n);
if (is_overlap(a.s, a.s + a.d, b.t - b.d, b.t)) add(i, j), add(j + n, i + n);
if (is_overlap(a.t - a.d, a.t, b.s, b.s + b.d)) add(i + n, j + n), add(j, i);
if (is_overlap(a.t - a.d, a.t, b.t - b.d, b.t)) add(i + n, j), add(j + n, i);
}
为什么第二个循环里面是j小于i
一对 数 为了避免重复只考虑 一个方向吗,,
我好奇的把j改成了小于n
wa掉了,,
考虑考虑原理,, 这个时间段如果有了 这个婚礼 别的婚礼就不能 再出现在这个位置了
小灯泡亮了
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
wedding a=w[i],b=w[j];
if(is_overloap(a.s,a.s+a.d,b.s,b.s+b.d ))add(i,j+n),add(j,i+n);
if(is_overloap(a.s,a.s+a.d,b.t-b.d,b.t ))add(i,j),add(j+n,i+n);
if(is_overloap(a.t-a.d,a.t,b.s,b.s+b.d ))add(i+n,j+n),add(j,i);
if(is_overloap(a.t-a.d,a.t,b.t-b.d,b.t ))add(i+n,j),add(j+n,i);
}
}
成功ac!
边数增加了一倍,时间也增加了一倍