如果你使用了可删堆,并且重载了小于号和等号。
重载小于号时,除了比较等效节点的权值大小外,还要对其他每个结构体元素进行大小比较。否则,会在可删堆删除元素时出错。
以下的代码是错误的:
struct no{
int sum,siz,u;
}c[N];
bool operator <(const no &n1,const no &n2){return n1.sum*n2.siz<n2.sum*n1.siz;}
bool operator ==(const no &n1,const no &n2){return n1.u==n2.u&&n1.sum==n2.sum&&n1.siz==n2.siz;}
因为假设你要删除两个元素,它们的 sum×siz 相等,那么可能会导致你的删除堆和保留堆的堆顶元素不完全相同,这样你无法删掉它,就会出错。
以下的代码是正确的:
struct no{
int sum,siz,u;
}c[N];
bool operator <(const no &n1,const no &n2){return n1.sum*n2.siz==n2.sum*n1.siz? (n1.sum==n2.sum? n1.u<n2.u: n1.sum>n2.sum): n1.sum*n2.siz<n2.sum*n1.siz;}
bool operator ==(const no &n1,const no &n2){return n1.u==n2.u&&n1.sum==n2.sum&&n1.siz==n2.siz;}