萌新求助wqs二分
查看原帖
萌新求助wqs二分
66511
DPair楼主2021/3/4 15:46

初学wqs二分,不懂就问。

为什么跑克鲁斯卡尔最小生成树的时候边的排序方式与答案有关啊,

就是如果这么排序:(val 是边权,col 是颜色,我这里为了方便后面反转了一下颜色的数字即 1 是白 0 是黑,最终求的还是白边)

struct EDGE{
    int val, u, v, col;
    inline bool operator < (const EDGE &tmp) const{return val < tmp.val || (val == tmp.val && col > tmp.col);}
}e[E];

是对的

但是如果这样:

struct EDGE{
    int val, u, v, col;
    inline bool operator < (const EDGE &tmp) const{return val < tmp.val || (val == tmp.val && col < tmp.col);}
}e[E];

就会 WA 35pts

求大佬指导/kel

2021/3/4 15:46
加载中...