其实就是有向的最小生成树
写了一个下午,因为不想写矩阵,V*V的空间不适用V大的题目,所以改来改去,改成存边的形式,其实想想存边的复杂度也是O(VE),图大的话也是需要挺高复杂度的,而且矩阵虽然说是O(V3),但是有很多地方continue的,所以一般矩阵形式也就够用了- -
算法说白了比较简单,分三步,如下:

  1. 每个点找其最小的入边In[v] ? 如果有除跟节点以外的点找不到入边,则无解 : 否则答案累加In[v]
  2. 看看有没有环 ? 无环则已经找到解,返回答案 : 将环缩点
  3. 重新构图,每条边[u->v]的权值减去In[v],然后重复第一步

(更多…)

Popularity: 7% [?]