警示后人
查看原帖
警示后人
658751
xueyuhui917楼主2024/9/8 18:55

如果你只 AC 了 Subtask 2 的 6 pts,并且采用先把边排序一遍再从小到大挨个加边的办法,自认为没有什么问题,请检查以下你的排序所用的比较函数,是否是类似于以下的写法:

bool cmp(eg X,eg Y)//eg 是边的结构体,有u,v,w,c四个成员,分别表示这条边的起点、终点(当然由于是无向图,也可以看成这条边的两个端点)、长度、维护费用
{
  return X.w<Y.w;
}

如果是,请改成:

bool cmp(eg X,eg Y)
{
  if(X.w==Y.w)return X.c<Y.c;
  return X.w<Y.w;
}

举个例子就能发现问题。假设有一张图,只有两个点两条边,一条 u=1,v=2,w=1,c=3u=1,v=2,w=1,c=3,另一条 u=1,v=2,w=1,c=2u=1,v=2,w=1,c=2,那么按照第一种排序方法,这两条边被视作相等,顺序不确定,因此算出来的答案可能是 33,但是显然正确答案是 22。按照第二种排序方法就不会有此问题。

2024/9/8 18:55
加载中...