题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
Python 代码
import sys
N = 510
M = 100010
g = [[sys.maxsize for _ in range(N)] for _ in range(N)]
dist = [sys.maxsize]*N
#dist[1] = 0
St = [False]*N
n,m = map(int, input().split())
def Prim():
res = 0
for i in range(n):
t = -1
for j in range(1, n+1):
if not St[j] and (t == -1 or dist[j] < dist[t]):
t = j
St[t] = True
if i and dist[t] == sys.maxsize:return -1
if i : res += dist[t]
for j in range(1, n+1):
dist[j] = min(dist[j], g[t][j])
return res
if __name__ == "__main__":
for i in range(m):
u,v,w = map(int, input().split())
g[u][v] = min(g[u][v], w)
g[v][u] = min(g[v][u], w)
t = Prim()
if t == -1:print("impossible")
else:print(t)
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla