好久没写题解了……
题目描述:有N(1≤N≤2000)个节点,M(1≤M≤10000)条边。你要保留一些边,使得这个图连通且最大的边最小,输出最大边。
解题思路:→_→将边按权值从大到小排序,枚举从头开始删的边数~每次判一遍是否联通,感觉这样很对的说~,→_→理想中的最坏情况时间复杂度会到达O(NM)即遍历删几条边的复杂度*bfs复杂度,啊咧不会超啊→_→,不过我用的是更快的方法↓
好久没写题解了……
题目描述:有N(1≤N≤2000)个节点,M(1≤M≤10000)条边。你要保留一些边,使得这个图连通且最大的边最小,输出最大边。
解题思路:→_→将边按权值从大到小排序,枚举从头开始删的边数~每次判一遍是否联通,感觉这样很对的说~,→_→理想中的最坏情况时间复杂度会到达O(NM)即遍历删几条边的复杂度*bfs复杂度,啊咧不会超啊→_→,不过我用的是更快的方法↓
Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com