如果你被hack数据hack

hack数据如下
input

CPP

output

CPP

第一条最短路为 1−2−8−4−5−6，第二条为 7−5−4−8 时，公共路径长度最大，为 6 。

你WA的原因大概率是方向一致性处理不当，导致了方向不一致的边被错误连接

一种合理的做法：

CPP

for (int d1 = 0; d1 < 2; d1++) {      // 第一条路径方向
    for (int d2 = 0; d2 < 2; d2++) {  // 第二条路径方向
        // 只连接在当前方向组合下方向一致的边
        if ((d1==0 && in1_uv && d2==0 && in2_uv) || 
            (d1==0 && in1_uv && d2==1 && in2_vu) ||
            (d1==1 && in1_vu && d2==0 && in2_uv) || 
            (d1==1 && in1_vu && d2==1 && in2_vu)) {
            // 建图...
        }
    }
}

通过枚举4种方向确保边不重复

事实上

设公共路径为P = {e₁, e₂, ..., eₖ}，其中eᵢ = (uᵢ, uᵢ₊₁)

对于路径1，要么：

CPP

所有eᵢ都是uᵢ→uᵢ₊₁（正向）

要么

CPP

所有eᵢ都是uᵢ₊₁→uᵢ（反向）

对于路径2，同样要么全部正向，要么全部反向。

因此只有四种可能的组合：

1.路径1正向 + 路径2正向

2.路径1正向 + 路径2反向

3.路径1反向 + 路径2正向

4.路径1反向 + 路径2反向

因此枚举四个方向可以得到正确答案。

如果你被hack数据hack

讨论操作

回复

相关推荐

如果你被hack数据hack