如果你只 AC 了 Subtask 2 的 6 pts,并且采用先把边排序一遍再从小到大挨个加边的办法,自认为没有什么问题,请检查以下你的排序所用的比较函数,是否是类似于以下的写法:
bool cmp(eg X,eg Y)
{
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=3,另一条 u=1,v=2,w=1,c=2,那么按照第一种排序方法,这两条边被视作相等,顺序不确定,因此算出来的答案可能是 3,但是显然正确答案是 2。按照第二种排序方法就不会有此问题。