图论基础算法python模板

Chuanhua Yu 发布于

最后更新于

图论

Fast Input/Output

fast output

1
2
for i in range(10):   
	sys.stdout.write(str(i)+"\n")

手动加栈

1
2
import sys
sys.setrecursionlimit(1000000)

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n,m = map(int,input().split())
head = [i for i in range(n+1)]
ver,edge,nxt = [0]*(2*m+1),[0]*(2*m+1),[0]*(2*m+1)
tot = 0   #为异或求反向边做铺垫

def add(x, y, z):
    global tot
    tot += 1
    ver[tot], edge[tot] = y, z
    nxt[tot], head[x] = head[x], tot

# 遍历 x 的出边
i = head[x]
while i:
    y,z = ver[i],edge[i]
    i = nxt[i]

z = edge[i^1]
"""存的是edge[i] 的反向边"""

有向无环图拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
g = {i:[] for i in range(1,n+1)}
deg = [0]*(n+1)  #记录入度
for _ in range(m):
    u,v,w = map(int, sys.stdin.readline().split())
    g[u].append((v,w))
    deg[v] += 1
ls, ans = [], []
q = deque()
for i in range(1,n+1):
    if deg[i] == 0:
        q.append(i)
while q:
    x = q.popleft()
    for y,w in g[x]:
        deg[y]-=1
        if deg[y] == 0: q.append(y)

例题：NOIP2003神经网络

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
from collections import deque 

n,m = map(int, sys.stdin.readline().split())
c,u,deg = [0]*(n+1), [0]*(n+1), [0]*(n+1)
g = {i:[] for i in range(1,n+1)}
for i in range(1,n+1):
    c[i],u[i] = map(int, sys.stdin.readline().split())
    if c[i] == 0:
        c[i] -= u[i]
for _ in range(m):
    x,y,z = map(int, sys.stdin.readline().split())
    g[x].append((y,z))
    deg[y] += 1

q = deque()
for i in range(1,n+1):
    if deg[i] == 0: q.append(i)
while q:
    x = q.popleft()
    for y,w in g[x]:
        deg[y] -= 1
        c[y] += w*c[x] if c[x] > 0 else 0
        if deg[y] == 0:
            q.append(y)
flag = True
for i in range(1,n+1):
    if len(g[i]) == 0 and c[i] > 0:
        print(i,c[i])
        flag = False
if flag: print("NULL")

NOIP2015菜肴制作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
import heapq

t = int(sys.stdin.readline())
while t > 0:
    t -= 1
    n,m = map(int, sys.stdin.readline().split())
    g = {i:[] for i in range(1,n+1)}
    deg = [0]*(n+1)
    for _ in range(m):
        x,y = map(int, sys. stdin.readline().split())
        g[y].append(x)
        deg[x] += 1
    ans, q = [], []
    for i in range(1,n+1):
        if deg[i] == 0: heapq.heappush(q,-i)  # 入度为0 表示没有限制 i 必须得在哪个前面做， 所以应该是每个连通块中最后做的
    while q:
        x = -heapq.heappop(q)  # 先处理最大的度为0的点， 让其最后做
        ans.append(x)
        for y in g[x]:     #遍历需要在 x 前做的点
            deg[y] -= 1
            if deg[y] == 0: heapq.heappush(q,-y)   #继续保持最大的在前面
    if len(ans) == n: print(*ans[::-1])
    else: print("Impossible!")

1、最短路模板：

堆优化Dijkstra：

1
2
3
4
5
6
7
8
9
10
11
12
13
def dijkstra(r = 1):
    heap = []  # 小顶堆实现优先队列
    dist[r] = 0
    heapq.heappush(heap, (0, r))
    while heap:
        start = heapq.heappop(heap)
        if vis[start[1]]: continue
        vis[start[1]] = True
        for i in g[start[1]]:  # 根据现找到的点start【1】更新其相连点的权重
            if dist[i[0]] > dist[start[1]] + i[1]:  # 判断是否松弛
                dist[i[0]] = dist[start[1]] + i[1]  # 松弛边
                heapq.heappush(heap, (dist[i[0]], i[0]))  # 将松弛过的新边权值加入堆
    return dist[n]

朴素Dijkstra用于稠密图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
g = [[inf if i != j else 0 for i in range(N)] for j in range(N)]   #groph
st = [0 for _ in range(N)]
dist = [inf for _ in range(N)]

def dijkstra():
    """朴素dijkstra算法 O(n^2)用于稠密图"""
    dist[1] = 0
    for i in range(n):
        t = -1
        for j in range(1, n+1):
            if not st[j] and (t == -1 or dist[t] > dist[j]):
                t = j
        st[t] = 1
        for j in range(1, n+1):
            dist[j] = min(dist[j], dist[t] + g[t][j])
    return dist[n]

Bellman-Ford：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys

n,m = map(int, sys.stdin.readline().split())
g = {i:[] for i in range(1, n+1)}
for _ in range(m):
    u,v,w = map(int, sys.stdin.readline().split())
    g[u].append((v, w))
inf = float("inf")
dist = [inf for _ in range(n+1)]
pi = [i for i in range(n+1)]  #记录最短路径树，记录该结点的前驱结点
def bellman_ford(G, r = 1):
    dist[r] = 0
    for j in range(1,n):
        for i in range(1, n+1):    #遍历所有边
            for x in G[i]:
                if dist[x[0]] > dist[i] + x[1]:
                    dist[x[0]] = dist[i] + x[1]
                    pi[x[0]] = i
    for i in range(1, n+1):
        for v,w in G[i]:
            if dist[v] > dist[i] + w:
                return False
    return True
bellman_ford(g)
print(dist[n])

SPFA:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
from collections import deque
"""堆优化的Bellman-Ford算法  也叫SPFA算法"""
inf = float("inf")
n,m = map(int, sys.stdin.readline().split())
g = {i:[] for i in range(1,n+1)}
vis = [False] * (n+1)  #保存判断点是否在队列里
dist = [inf] * (n+1)
for _ in range(m):
    u,v,w = map(int, sys.stdin.readline().split())
    g[u].append((v,w))

def spfa(r = 1):
    q = deque()
    dist[r] = 0
    q.append(r)
    vis[r] = True
    while q:
        u = q.popleft()
        vis[u] = False
        for v,w in g[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if not vis[v]:
                    q.append(v)
                    vis[v] = True

SPFA求负环：

(1)统计每个点入队的次数，如果某个点入队n次，则说明存在负环。

(2)统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则有负环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def spfa():
    dist = [1e9]*(n+1)
    dist[1] = 0
    cnt = [0]*(n+1)
    vis = [1]*(n+1)
    q = deque()
    for i in range(1,n+1): q.append(i)
    while q:
        x = q.popleft()
        vis[x] = 0
        for y,w in g[x]:
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
                cnt[y] = cnt[x] + 1
                if cnt[y] >= n: return 1
                if vis[y] == 0:
                    q.append(y) 
                    vis[y] = 1
    return 0

Floyd:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def floyd(w):
    """Floyd算法求所有结点对的最短路径，时间复杂度：O(V^3)"""
    d = deepcopy(w)
    for k in range(1, n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

"""Floyd求传递闭包"""
inf = float("inf")
n,m = map(int, sys.stdin.readline().split())
g = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    x,y = map(int, sys.stdin.readline().split())
    g[x][y] = 1

def floyd():
    for k in range(1,n+1):
        for x in range(1,n+1):
            for y in range(1,n+1):
                g[x][y] |= g[x][k] & g[k][y]

例题

通信线路（分层图最短路）

法一：运用动态规划的思想，不同免费的边数对应不同的层，每层图结构相同，其中 用dist[v][j]存从1到v免费j条边的最短路(题意中是路径中第j+1大的边权)。
对于 j 不变 dist[v][j] = max(dist[u][j], w[u to v]).
对于 j += 1 的情况， 可以得到 dist[v][j+1] = min(dist[u][j], dist[v][j+1]
详见代码和注释。

法二：定义一个t表示答案，将边权大于t的看为1，将边权小于等于t的堪为0，求一边对短路(双端队列BFS），dist[n]就为答案为t时所需免费线路的条数。
if t <= k: r = mid
else: l = mid + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import sys
import heapq
from collections import deque
"""解法1: 分层图 + 堆优化的dijkstra, 运用动态规划的思想"""

inf = float("inf")
n,m,k = map(int, sys.stdin.readline().split())
g = {i:[] for i in range(1, n+1)}
vis = [[False] * (k + 1) for _ in range(n + 1)]
dist = [[inf] * (k + 1) for _ in range(n + 1)]

for _ in range(m):  #存一层的图，因为每层图结构是一样的
    u,v,w = map(int, sys.stdin.readline().split())
    g[u].append((v, w))
    g[v].append((u, w))

def dijkstra(r = 1):
    q = []
    dist[r][0] = 0
    heapq.heappush(q, (0, r, 0))    # (d, 点的编号, 第几层) 不同的层数代表免费几条边
    while q:
        x,i,j = heapq.heappop(q)
        if vis[i][j]: continue
        vis[i][j] = True
        for v,w in g[i]:
            if dist[v][j] > max(x, w):
                dist[v][j] = max(x, w)
                heapq.heappush(q, (dist[v][j], v, j))
            if j < k and dist[v][j+1] > x:
                dist[v][j+1] = dist[i][j]
                heapq.heappush(q, (dist[v][j+1], v, j+1))

dijkstra(1)
ans = inf
for i in range(k+1):
    ans = min(dist[n][i], ans)
print(ans if ans != inf else -1)


"""解法2: 双向广搜 + 二分答案"""
def solve(t):
    dist = [inf] * (n + 1)
    dist[1] = 0
    q = deque()
    q.append(1)
    while q:
        u = q.popleft()
        for v,w in g[u]:
            w = 0 if w <= t else 1
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if w == 0: q.appendleft(v)
                else: q.append(v)
    return dist[n] <= k


l,r = 0, 1000001
while (l < r): #二分答案
    mid = (l+r)//2
    if solve(mid): r = mid
    else: l = mid + 1
print(l if l != 1000001 else -1)

最优贸易

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import sys
from queue import Queue

inf = float("inf")
n,m = map(int, sys.stdin.readline().split())
g = {i:[] for i in range(1,n+1)}
G = {i:[] for i in range(1,n+1)}
ls = [0]
ls.extend(list(map(int, sys.stdin.readline().split())))
for _ in range(m):
    x,y,z = map(int, sys.stdin.readline().split())
    g[x].append(y)
    G[y].append(x)
    if z == 2:
        G[x].append(y)
        g[y].append(x)
dmin, dmax = [101]*(n+1), [0] * (n+1)

def spfa(r, flag):
    vis = [False]*(n+1)
    q = Queue()
    q.put(r)
    vis[r] = True
    if flag: dmin[r] = ls[r]
    else: dmax[r] = ls[r]
    while not q.empty():
        x = q.get()
        vis[x] = False
        if flag:
            for v in g[x]:
                tmp = min(ls[v],dmin[x])
                if dmin[v] > tmp:
                    dmin[v] = tmp
                    if not vis[v]:
                        q.put(v)
                        vis[v] = True
        else:
            for v in G[x]:
                tmp = max(ls[v], dmax[x])
                if dmax[v] < tmp:
                    dmax[v] = tmp
                    if not vis[v]:
                        q.put(v)
                        vis[v] = True
spfa(1, True)
spfa(n, False)
ans = -1
for i in range(1,n+1):
    if ans < dmax[i] - dmin[i]: ans = dmax[i] - dmin[i]
print(ans)

道路与航线(拓扑排序套Dijkstra)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import sys
from heapq import *
from collections import deque

sys.setrecursionlimit(10005)
inf = float("inf")
n,r,p,s = map(int,sys.stdin.readline().split())
g = {i:[] for i in range(n+1)}
dist,vis,deg = [inf]*(n+1), [False]*(n+1), [0]*(n+1)
color,node,cnt = [0]*(n+1), [[] for _ in range(n+1)], 0   #用于染色统计连通块
for _ in range(r):
    a,b,c = map(int,sys.stdin.readline().split())
    g[a].append((b,c,0))
    g[b].append((a,c,0))
for _ in range(p):
    a,b,c = map(int,sys.stdin.readline().split())
    g[a].append((b,c,1))

def dfs(x):
    color[x] = cnt
    node[cnt].append(x)
    for y,w,z in g[x]:
        if z == 1: continue
        if color[y]: continue
        dfs(y)

for i in range(1,n+1):
    if color[i]: continue
    cnt += 1
    dfs(i)

for x in range(1,n+1):
    for y,w,z in g[x]:
        if z == 1: deg[color[y]] += 1
q = deque()
for i in range(1, cnt+1):
    if deg[i] == 0:
        q.append(i)
        
def dijkstra(k):
    heap = []
    for x in node[k]:
        heappush(heap, (dist[x], x))
    while heap:
        _,x = heappop(heap)
        if vis[x]: continue
        vis[x] = True
        for y,w,z in g[x]:
            if z == 0:  #内层Dijkstra
                if dist[y] > dist[x] + w:
                    dist[y] = dist[x] + w
                    heappush(heap, (dist[y],y))
                continue
            deg[color[y]] -= 1   #外层toposort
            dist[y] = min(dist[y], dist[x] + w)
            if deg[color[y]] == 0: q.append(color[y])
        
dist[s] = 0
while q:
    k =q.popleft()
    dijkstra(k)

for i in range(1,n+1):
    print(dist[i] if dist[i] != inf else "NO PATH")

观光之旅（Floyd求最小环）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""有向图的最小环问题只需要枚举起点，跑dijkstra
dist[i] = 0, 扩展之后， 把起点 i ,dist[i] = inf,
再次从队列中弹出 i 时，可得到从 i 到 i 的最短路，即最小环。
但无向图得把无向边排除
"""
import sys
from copy import deepcopy

inf = float("inf")
n,m = map(int, sys.stdin.readline().split())
g = [[inf]*(n+1) for _ in range(n+1)]
pos = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    u,v,w = map(int, sys.stdin.readline().split())
    g[u][v] = min(w, g[u][v])
    g[v][u] = min(w, g[v][u])
d = deepcopy(g)
path = []
def get_path(x, y):   #获得从 x 到 z 的路径，pos[x][y] = floyd更新最短路是选取的中间节点的最大编号
    if pos[x][y] == 0: return
    k = pos[x][y]
    get_path(x, k)  #递归一直到 x 的 下一节点为 k 时
    path.append(k)
    get_path(k, y)

ans = inf
for k in range(1,n+1):
    for i in range(k):
        for j in range(i+1,k):
            if d[i][j] + g[j][k] + g[k][i] < ans:
                ans = d[i][j] + g[j][k] + g[k][j]
                path.clear()
                path.append(i)
                get_path(i, j)
                path.append(j)
                path.append(k)
    for i in range(1,n+1):
        for j in range(1,n+1):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
                pos[i][j] = k     #记录中转点(1~k-1)

排序（Floyd解传递闭包）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import sys

ls = list(".ABCDEFGHIJKLMNOPQRSTUVWXYZ")
def floyd():
    for k in range(1, n+1):
        for x in range(1,n+1):
            for y in range(1,n+1):
                g[x][y] |= g[x][k] & g[k][y]

def get_sort():
    ans = []
    vis = [0] * (n+1)
    for i in range(n-1, -1, -1):
        for x in range(1, n+1):
            if vis[x]: continue
            cnt = 0
            for y in range(1, n+1):
                if g[x][y]: cnt += 1
            if cnt == i:
                ans.append(ls[x])
                vis[x] = 1
                break
    ans = ''.join(ans) + '.'
    return ans
                
def cheak():
    flag = 1
    for i in range(1,n+1):
        for j in range(1,n+1):
            if (g[i][j] == 1 and g[j][i] == 1): return 2
            if (g[i][j] == 0 and g[j][i] == 0 and j != i): flag = 3
    return flag

while True:
    n,m  = map(int, sys.stdin.readline().split())
    if n == m and n == 0: break
    g = [[0]*(n+1) for _ in range(n+1)]
    flag, t = 0, m
    for i in range(1,m+1):
        a,b = sys.stdin.readline().strip().split('<')
        a = ord(a) - ord('A') + 1
        b = ord(b) - ord('A') + 1
        g[a][b] = 1
        floyd()
        num = cheak()
        if num == 2:
            flag = 2
            t = min(i,t)
        elif num == 3:
            flag = 3
        else:
            flag = 1
            t = i
            break
    if flag == 3:
        print("Sorted sequence cannot be determined.")
    elif flag == 2:
        print(f'Inconsistency found after {t} relations.')
    else:
        print(f'Sorted sequence determined after {t} relations:', end = ' ')
        print(get_sort())
        for i in range(m-t):
            s = sys.stdin.readline()

花费与流量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""New OJ P1717  带流限制的最短路径问题"""
import sys
import heapq

inf = float("inf")
n,m = map(int, sys.stdin.readline().split())
g = {i:[] for i in range(1, n+1)}
flow = [0]*(m+1)

for i in range(1, m+1):
    u,v,c,f = map(int, sys.stdin.readline().split())
    g[u].append((v,c,f))
    g[v].append((u,c,f))
    flow[i] = f

def dijkstra(x):
    """带流限制的dijkstra算法"""
    dist = [inf] * (n + 1)
    vis = [False] * (n + 1)
    dist[1] = 0
    q = []
    heapq.heappush(q, (0, 1))
    while q:
        start = heapq.heappop(q)
        if vis[start[1]]: continue
        vis[start[1]] = True
        for i in g[start[1]]:
            if i[2] < x: continue
            if dist[i[0]] > dist[start[1]] + i[1]:
                dist[i[0]] = dist[start[1]] + i[1]
                heapq.heappush(q, (dist[i[0]], i[0]))
    return dist[n] if dist[n] != inf else -1

best_f, best_w = 0, 1
for i in range(1, m+1):
    f = flow[i]
    w = dijkstra(f)
    if w != -1:
        if f * best_w > best_f * w:
            best_f, best_w = f, w
print(1000000 * best_f // best_w)

2、MST模板

Kruskal：O(mlogm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys

n,m = map(int, sys.stdin.readline().split())
g = {i:[] for i in range(1,n+1)}
edge = []
for _ in range(m):
    u,v,w = map(int, sys.stdin.readline().split())
    g[u].append((v,w))
    edge.append((w,u,v))
ls = [i for i in range(n+1)]
ans = 0
edge.sort()
def find_set(x):  #带路径压缩的find_set
    if x == ls[x]: return x
	ls[x] = find_set(ls[x])
    return ls[x]
for i in range(m):
    w,u,v = edge[i]
    x = find_set(u)
    y = find_set(v)
    if x != y:
        ls[y] = x   
        ans += w

Prim：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys

inf = float("inf")
n,m = map(int, sys.stdin.readline().split())
g = [[inf] * (n+1) for _ in range(n+1)]
for _ in range(m):
    x,y,z = map(int, sys.stdin.readline().split())
    g[x][y] = z
    g[y][x] = z
vis = [False] * (n+1)
mst = [inf] * (n+1)
mst[1] = 0
for i in range(1, n):
    x = 0
    for j in range(1,n+1):
        if vis[j]: continue
        if x == 0 or mst[j] < mst[x]: x = j
    vis[x] = True
    for y in range(1, n+1):
        if not vis[y] and mst[y] > g[x][y]:
            mst[y] = g[x][y]
ans = 0
for i in range(1,n+1):
    ans += mst[i]
print(ans)

堆优化的Prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
import heapq

def prim():
    ans = 0
    vis[1] = True
    for y,w in g[1]:
        heapq.heappush(q,(w,y))
    while q:
        tmp,x = heapq.heappop(q)
        if vis[x]: continue
        vis[x] = True
        ans += tmp
        for y,w in g[x]:
            if vis[y]: continue
            heapq.heappush(q, (w,y))
    print(ans)

n,m = map(int, sys. stdin.readline().split())
g = {i:[] for i in range(1,n+1)}
for _ in range(m):
    a,b,c = map(int, sys.stdin.readline().split())
    g[a].append((b,c))
    g[b].append((a,c))
vis = [False] * (n+1)
q = []
prim()

MST例题

走廊泼水节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys

def find_set(x):
    if x == ls[x][0]: return x
    return find_set(ls[x][0])

t = int(sys.stdin.readline())
while t > 0:
    t -= 1
    ans = 0
    n = int(sys.stdin.readline())
    g = {i: [] for i in range(1, n + 1)}
    edge = []
    for _ in range(n - 1):
        u, v, w = map(int, sys.stdin.readline().split())
        g[u].append((v, w))
        g[v].append((u, w))
        edge.append((w, u, v))
    ls = [(i, 1) for i in range(n + 1)]
    edge.sort()
    for i in range(n - 1):
        w, u, v = edge[i]
        x = find_set(u)
        y = find_set(v)
        if x != y:
            j, k = ls[y]
            l, r = ls[x]
            ans += (r * k - 1) * (w + 1)
            ls[x] = (x, k + r)
            ls[y] = (x, k + r)
    print(ans)

野餐规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import sys

#初始化
inf = float("inf")
vis, c = [False] * 25, [False] * 25  # c : color
mst = [inf] * 25
s, ans, deg =0, 0, 0       # s, 最小生成树的权值, 统计Park的度数
conn = [0]*25    #connection  记录每个点连的是哪个点
dic = {"Park":1}   #字符串映射为整数
g, tree = [[inf]*25 for _ in range(25)], [[inf]*25 for _ in range(25)]  #邻接矩阵, 记录树的路径，MST对应的邻接矩阵
ver, p = [0]*25, 0
f, fx, fy = [0]*25, [0]*25, [0]*25   # (fx[i], fy[i]) 是从1 到 i 路径上边权最大的边, 边权为 f[i]

# 输入
n = int(sys.stdin.readline())
cnt = 1
for _ in range(n):
    a,b,z = sys.stdin.readline().split()
    if a != "Park" and a not in dic:
        cnt += 1
        dic[a] = cnt
    if b != "Park" and b not in dic:
        cnt += 1
        dic[b] = cnt
    g[dic[a]][dic[b]] = min(int(z), g[dic[a]][dic[b]])
    g[dic[b]][dic[a]] = min(int(z), g[dic[b]][dic[a]])
s = int(sys.stdin.readline())

#Prim算法
def prim(root):
    """对 ver中的 p个点求 mst"""
    global ans, p, deg
    mst[root] = 0
    for i in range(1, p+1):
        x = 0
        for j in range(1, p+1):
            if not vis[ver[j]] and (x == 0 or mst[ver[x]] > mst[ver[j]]): x = j
        vis[ver[x]] = True    #找到最小的 mst[ver[x]],加入已选集合
        for j in range(1, p+1):    #更新生成树的集合
            y = ver[j]
            if not vis[y] and mst[y] > g[ver[x]][y]:
                mst[y], conn[y] = g[ver[x]][y], ver[x]
    closest = root
    for i in range(1, p+1):
        if ver[i] == root: continue
        x = ver[i]
        ans += mst[x]
        tree[conn[x]][x] = tree[x][conn[x]] = mst[x]
        if g[1][closest] > g[1][x]: closest = x
    deg += 1  # 每个连通块与1连一条边
    ans += g[1][closest]
    tree[1][closest] = tree[closest][1] = g[1][closest]

def dfs(x):   #找连通块
    global p
    ver[p+1],p = x, p+1
    c[x] = True
    for y in range(1, cnt+1):
        if g[x][y] != inf and not c[y]: dfs(y)

def prim_for_all_comp():
    global p
    for i in range(2,25):
        vis[i], mst[i] = False, inf
    c[1] = True
    vis[1] = True
    for i in range(2,cnt+1):
        if not c[i]:
            p = 0
            dfs(i)
            # ver中保存了一个连通块里的点
            prim(i)  #对这个连通块求prim

def dp(x):
    vis[x] = True
    for y in range(2, cnt + 1):
        if tree[x][y] != inf and not vis[y]:
            if f[x] > tree[x][y]:
                f[y] = f[x]
                fx[y],fy[y] = fx[x], fy[x]  #方案不变
            else:
                f[y] = tree[x][y]
                fx[y], fy[y] = x, y
            dp(y)

def solve():
    """用于加边"""
    global ans
    min_val, mini = inf, 0
    for i in range(2,cnt+1):  #枚举非树边(1,i)， 看加哪条边
        if tree[1][i] != inf or g[1][i] == inf: continue
        # 加入非树边(1,i), 删除数边(fx[i], fy[i])
        if g[1][i] - tree[fx[i]][fy[i]] < min_val:
            min_val = g[1][i] - tree[fx[i]][fy[i]]
            mini = i
    if min_val >= 0: return False
    ans += min_val
    tree[fx[mini]][fy[mini]] = tree[fy[mini]][fx[mini]] = inf
    tree[1][mini] = tree[mini][1] = g[1][mini]
    #重新计算以mini[i] 为根的子树的状态
    f[mini] = g[1][mini]
    fx[mini], fy[mini] = 1, mini
    for i in range(2,25):
        vis[i] = False
    dp(mini)
    return True

"""主函数"""
# 删除1号点，找出每个连通块，各自求Prim
prim_for_all_comp()
for i in range(2,25):
    vis[i] = False
dp(1)  #树上动规
while deg < s:
    if not solve(): break
    deg += 1
print(f'Total miles driven: {ans}')

3、树的直径与最近公共祖先模板

求直径的两种求法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import sys
from collections import deque

inf = float("inf")
n = int(sys.stdin.readline())
g = {i:[] for i in range(1,n+1)}
for _ in range(n-1):
    u,v,w = map(int, sys.stdin.readline().split())
    g[u].append((v,w))

"""树形DP求树的直径"""
d, res = [0]*(n+1), -inf   #d[x]表示从点x出发走向以x为根的子树，能够到达最远节点的距离
vis = [False] * (n+1)
def dp(x):
    global res
    vis[x] = True
    for y, w in g[x]:
        if vis[y]: continue
        dp(y)
        res = max(ans,d[x] + d[y] + w)  
# d[x] + d[y] + w = d[yi] + edge[x,yi] + edge[x,yj] + d[yj]   j < i
        d[x] = max(d[x], d[y] + w)  
# 在枚举到i时d[x]恰好保存了从x到以yj为根的子树最远距离，d[x] = max{d[yj] + edge[e,yj]| j < i}


"""两次BFS求树的直径"""
d,pre = [0]*(n+1),[i for i in range(n+1)]  #pre记录了路径
def bfs(r):
    q = deque()
    q.append(r)
    while q:
        x = q.popleft()
        for y in g[x]:
            if d[y]: continue
            dist[y] = dist[x] + 1
            pre[y] = x
            q.append(y)
    ans = 1
    for i in range(2,n+1):
        if d[ans] < d[i]: ans = i
    return ans

p = bfs(1)
d = [0]*(n+1)
q = bfs(p)
print(d[q])

例题：

1、巡逻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sys
from queue import Queue

inf = float("inf")
n,k = map(int, sys.stdin.readline().split())
g = {i:{} for i in range(1,n+1)}
dist, pre = [0]*(n+1), [i for i in range(n+1)]
q = Queue()
for _ in range(n-1):
    x,y = map(int, sys.stdin.readline().split())
    g[x][y] = g[y][x] = 1

def bfs(r):
    q.put(r)
    while not q.empty():
        x = q.get()
        for y in g[x]:
            if dist[y]: continue
            dist[y] = dist[x] + 1
            pre[y] = x
            q.put(y)
    ans = 1
    for i in range(2,n+1):
        if dist[ans] < dist[i]: ans = i
    return ans

def dp(x):
    global res
    vis[x] = True
    for y in g[x]:
        if vis[y]: continue
        dp(y)
        res = max(res,d[x] + d[y] + g[x][y])
        d[x] = max(d[x], d[y] + g[x][y])

p = bfs(1)
dist = [0]*(n+1)
q = bfs(p)
ans = 2*(n-1) - dist[q] + 1
if k == 2:
    while q != p:
        g[pre[q]][q] = g[q][pre[q]] = -1
        q = pre[q]
    d, res = [0] * (n + 1), -inf
    vis = [False] * (n + 1)
    dp(1)
    ans = ans - res + 1
print(ans)

2、树网的核

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import sys
from queue import Queue

n,s = map(int, sys.stdin.readline().split())
g = {i:{} for i in range(1,n+1)}
for _ in range(n-1):
    x,y,z = map(int, sys.stdin.readline().split())
    g[x][y] = z
    g[y][x] = z

pre,d = [0]*(n+1), [0]*(n+1)
dist,vis = [0]*(n+1),[False]*(n+1)
def bfs(r):
    q = Queue()
    q.put(r)
    while not q.empty():
        x = q.get()
        for y,w in g[x].items():
            if d[y] or y == r: continue
            d[y] = d[x] + w
            pre[y] = x
            q.put(y)
    ans = r
    for i in range(1,n+1):
        if d[i] > d[ans]: ans = i
    return ans

def dfs(r):
    d = 0
    for y,w in g[r].items():
        if vis[y]: continue
        vis[y] = True
        d = max(dfs(y)+w, d)
    return d

p = bfs(1)
d = [0]*(n+1)
q = bfs(p)

idx,ls = q,[]
while idx != p:
    vis[idx] = True
    ls.append(idx)
    idx = pre[idx]
vis[p] = True
ls.append(p)

for i in range(1,n+1):
    dist[i] = dfs(i)
max_ = max(dist)

ans = float("inf")
j = 0
for i in range(len(ls)):
    while j != len(ls)-1 and d[ls[i]] - d[ls[j+1]] <= s: j += 1
    ans = min(ans, max(d[q]-d[ls[i]], d[ls[j]]))
print(max(ans,max_))

LCA

smile是对你的礼貌

smile是对你的礼貌

在思维的迷宫里，有的人凭天生的灵感直奔终点； 有的人以持久的勤勉，铸造出适合自己的罗盘！

33
2
13
NOTICE

这是我的个人博客，主要发布一些算法竞赛相关题解和人工智能相关的技术与知识，页面最下面可以访问我的Github和知乎，可以通过下面链接访问我的CSDN https://blog.csdn.net/smile__everydays?spm=1000.2115.3001.5343

CATEGORYS
TAGS
DP Machine Learning XCPC div2 python模板 介绍 图匹配 图论 技术部寒假算法培训 最小生成树 牛客竞赛 蓝书 题目汇总