P5839-图论-Floyd算法

在搜刮中bfs只得当无权图
若是碰到有权图最简单的方法就是用毗邻矩阵-二维矩阵存储每个点对之间的权重,然后用floyd
1.毗邻矩阵

如果是二维输入权值的话直接append就好了

1. ma=[]
3. for i in range(m):
4.     ma.append(list(map(int,input().split())))

复制代码

点对输入环境的：
用INF初始化界说没有边无法到达
然后对每个点到自己界说为0，也就是没距离
同时用min读入来处理重边（i到j不止一条路，那么优先选短的）

1. INF=float('inf')
2. ma=[[INF]*n for _ in range(n)]
4. for i in range(n):
5.     ma[i][i]=0
7. for i in range(m):
8.     a,b,c=map(int,input().split())
9.     ma[a-1][b-1]=min(ma[a-1][b-1],c)
10.     ma[b-1][a-1]=min(ma[b-1][a-1],c)

复制代码

2.floyd算法

本质实在是动态规划
ma数组存储的是每个点之间的直接距离，并没有思量从中节点经过的环境
那么我们只需要再罗列在 i、j 点之间的所有大概点k，用min存储更小的途径

1. def floyd(ma):
2.     for k in range(m):
3.         for i in range(m):
4.             for j in range(m):
5.                 ma[i][j]=min(ma[i][j],ma[i][k]+ma[k][j])
6.     return ma

复制代码

如果原来的ma数组还会用到，那么最好复制一下ma 

1.         d=[[ma[i][j] for j in range(m)] for i in range(m)]

复制代码

注意：不能用dist=ma.copy()
因为二维数组的浅拷贝会导致对拷贝体做更改的时候会影响本体

1. a=[1,2,3]
2. a2=a.copy()
3. a2.append(4)
4. print(a,a2)
6. print()
8. b=[[1,2],[3]]
9. b2=b.copy()
10. b2[1].append(4)
11. print(b,b2)
13. '''输出
14. [1,2,3] [1,2,3,4]
15. [[1,2],[3,4]] [[1,2],[3,4]]
16. '''

复制代码

 P5839

P5839 [USACO19DEC] Moortal Cowmbat G - 洛谷
起首我们跑一边floyd得出最小代价

1. INF = float('inf')
3. n, m, k = map(int, input().split())
4. s = input()
5. ma = [list(map(int, input().split())) for _ in range(m)]
7. def floyd(ma):
8.     d = [[ma[i][j] for j in range(m)] for i in range(m)]
9.     for k in range(m):
10.         for i in range(m):
11.             for j in range(m):
12.                 d[i][j] = min(d[i][j], d[i][k] + d[k][j])
13.     return d
15. d = floyd(ma)

复制代码

背面就是得规划我们该如何变我们的字符串
dp状态: F[ i ]表现到i位置全部合法的最小代价
dp转移: F[ i ]=F[ j ]+k( i,j )        其中k( i,j )表现 i 到 j 全部改为一种颜色的最小代价，这里可以用前缀和举行预处理

2. #前缀和
3. su = [[0]*(n+1) for i in range(m)]
5. for i in range(m):
6.     for j in range(1, n+1):  # 从1开始到n
7.         su[i][j] = su[i][j-1] + d[ord(s[j])-ord('a')][i]
9. f = [INF]*(n+1)
10. f[0] = 0
11. mx = [0]*m
12. for i in range(k, n+1):
13.     for col in range(m):
14.         mx[col] = max(mx[col], su[col][i-k]-f[i-k])
15.     for col in range(m):
16.         f[i] = min(f[i], su[col][i]-mx[col])
17. print(f[n])

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。