专栏文章

题解：P12976 受力分析 Force

yy_kx_b
P12976题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip0qsti
此快照首次捕获于
2025/12/03 04:16
3 个月前
此快照最后确认于
2025/12/03 04:16
3 个月前
查看原文
赛时被硬控 2h 然后有一个处理（新建 dis 为 00 的辅助点）没想到，喜提 30 pts。
做法好像和官解不太一样……？
我们直入主题吧。
li,j⩽xi+yj⩽ri,jl_{i,j}\leqslant x_i+y_j\leqslant r_{i,j}，考虑先固定 xx，那么 yjy_j 的取值范围就是一系列平移之后的线段的交。
字典序要求先让 xix_i 尽可能小，所以考虑什么时候有解。考虑怎么处理 nn 个线段有交，猜当且仅当两两线段有交。（oi 为什么需要证明？猜就完事了！ 证明见文末。）
那么考虑两条线段有交的问题。对于同一个 jj 有 {(li,j−xi)⩽yj⩽(ri,j−xi)(li′,j−xi′)⩽yj⩽(ri′,j−xi′)\begin{cases}(l_{i,j}-x_i)\leqslant y_j\leqslant (r_{i,j}-x_i)\\(l_{{i^\prime},j}-x_{i^\prime})\leqslant y_j\leqslant (r_{{i^\prime},j}-x_{i^\prime})\end{cases}，两条线段有交那么 lmax⁡⩽rmin⁡l_{\max}\leqslant r_{\min} 即 {(li,j−xi)⩽(ri′,j−xi′)(li′,j−xi′)⩽(ri,j−xi)\begin{cases}(l_{i,j}-x_i)\leqslant (r_{{i^\prime},j}-x_{i^\prime})\\(l_{{i^\prime},j}-x_{i^\prime})\leqslant(r_{i,j}-x_i) \end{cases}，整理就是 xi−xi′⩾(li,j−ri′,j)x_i-x_{i^\prime}\geqslant (l_{i,j}-r_{{i^\prime},j}) 的形式。这是什么？差分约束！贺个板子先。O(n2)\mathcal O(n^2) 建图，spfa 最坏复杂度 O(nm)=O(n3)\mathcal O(nm)=\mathcal O(n^3)，基本没问题。
仔细一想，差分约束求出的就是天然最大解（不等式 disv⩽disu+wdis_v\leqslant dis_u+w 很多都取等了），但我们需要最小解，好办！xi−xi′⩾w⇔(−xi′)−(−xi)⩾wx_i-x_{i^\prime}\geqslant w\Leftrightarrow (-x_{i^\prime}) - (-x_i) \geqslant w，−x-x 最大解就是 xx 最小解了。然后把 xix_i 带回原式可以得到 yjy_j 的取值范围，最小值就出来了。
你说的对，但是需要 xi⩾0x_i\geqslant 0 怎么办？一开始容易想到平移（所有 xix_i 加一个数，所有 yjy_j 减这个数，解仍然合法），然后一交只有 30pts。事实上考虑比如最小解 (0,−1)(0,-1) 不合法，如果 (0,0)(0,0) 合法，你对最小解直接平移变成 (1,0)(1,0) 就不是最优解了。怎么办呢？注（看）意（题）到（解）！(−xi)⩽0+0(-x_i) \leqslant 0 + 0，那么新建一个点令其 dis 为 00 然后建边权为 00 的边就好了。
你说的对，但是需要 yj⩾0y_j\geqslant 0 怎么办？我还是采用平移的方法，但事后发现根本不会出现 yj<0y_j<0 的情况。事实上（感谢出题人 Comentropy），如果存在 yj<0y_j<0 那么 ∀i xi⩾li,j−yj⩾1\forall i\ x_i \geqslant l_{i,j}-y_j\geqslant1（因为 −yj>0,li,j⩾0-y_j>0,l_{i,j}\geqslant0），也就是说 xx 内没有 00，那么可以进行如下的调整：将所有 xix_i 减小 11 同时将所有 yjy_j 增大 11，调整后的解一定合法，与调整前解字典序最小矛盾。所以直接求出的 yjy_j 一定非负。
下面是我的实现：（完整代码见 R221749640）
CPP
// 注意 dis 要开 long long 不然负环走几圈早爆 int 了
#define rep(i, x, y) for(auto i = (x); i <= (y); i++)
int l[N][N], r[N][N];
int ans1[N], ans2[N];//即题目中的 x, y
int main() {
    scanf("%d", &n);
    rep(i, 1, n) rep(j, 1, n) scanf("%d", l[i] + j);
    rep(i, 1, n) rep(j, 1, n) scanf("%d", r[i] + j);
    rep(i, 1, n) rep(j, 1, n) if(i != j) {//此处 j 即为题解中 i', k 为题解中 j
        // xi - xj >= l(i,k) - r(j,k), (-xj) - (-xi) >= ~
        int p = -(1 << 30);
        rep(k, 1, n) p = max(p, l[i][k] - r[j][k]);
        //b - a >= x, a <= b - x, dis(i) <= dis(j) + (-x)
        add(j, i, -p);
    }
    rep(i, 1, n) add(n + 1, i, 0); //dis(u) <= dis(n + 1) ( = 0) + w (= 0)
    SPFA(n + 1);//dis(n+1) 天然为 0
    if(negative_loop) return puts("-1"), 0;//不要忘了main返回值是0！
    rep(i, 1, n) ans1[i] = -dis[i];
    int mn = *std::min_element(ans1 + 1, ans1 + n + 1);//注意不要写成 min(int*, int*)，后者在对指针取min（
    rep(i, 1, n) ans1[i] -= mn;//平移，使最小值为 0，防止求出 (1,1) 这种解
    rep(j, 1, n) {
        ans2[j] = -(1 << 30);
        rep(i, 1, n) ans2[j] = max(ans2[j], l[i][j] - ans1[i]);
    }
    assert(*std::min_element(ans2 + 1, ans2 + n + 1) >= 0);//proved.
    rangewriteln(ans1 + 1, ans1 + n + 1);
    rangewriteln(ans2 + 1, ans2 + n + 1);
    return 0;
}
撒花！
另外提供一个自造样例：
CPP
2
2 4
1 5
3 6
2 7
题面样例改了一个数，输出和题面样例一致。应该能很搞出一些错吧。
对于“nn 个线段有交当且仅当两两线段有交”的证明：充分性显，考虑必要性（如果 nn 个线段两两有交，那么这些线段就有交吗？）。注意到 nn 条线段的交就是 [lmax⁡,rmin⁡][l_{\max}, r_{\min}]，如果 nn 条线段没有交那么一定存在一个 ll 比另一个 rr 大，那么这两条线段就没有交，必要性得证。事实上推广到集合就不成立了（比如 {{1,2},{2,3},{1,3}}\big\{\{1,2\},\{2,3\},\{1,3\}\big\}）。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...