树与图的存储

邻接矩阵

g=[[float('inf')]*N for i in range(N)]
for i in range(1,n+1):
    g[i][i]=0

邻接表(链式前向星)

def add(a,b,c):#添加a向b的一条权值为c的边
    global idx
    e[idx]=b
    w[idx]=c
    ne[idx]=head[a]
    head[a]=idx
    idx+=1

e=[0]*M;ne=[0]*M;head=[-1]*N;idx=0;w=[0]*M

i=head[x]#遍历x出发的所有边
while i!=-1:
    j=e[i]
    d=w[i]
    i=ne[i]

拓扑排序(拓扑图<==>有向无环图)

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。

def add(a,b):
    global idx
    e[idx]=b
    ne[idx]=head[a]
    head[a]=idx
    idx+=1

def topsort():
    global hh,tt
    for i in range(1,n+1):
        if d[i]==0:
            tt+=1;q[tt]=i
    while hh<=tt:
        t=q[hh];hh+=1
        i=head[t]
        while i!=-1:
            j=e[i]
            d[j]-=1
            if d[j]==0:
                tt+=1;q[tt]=j
            i=ne[i]
    return tt==n-1

n,m=map(int,input().split())
N=n+10;M=m+10
e=[0]*M;ne=[0]*M;head=[-1]*N;idx=0
d=[0]*N;q=[0]*N;hh=0;tt=-1
for i in range(m):
    x,y=map(int,input().split())
    add(x,y)
    d[y]+=1
if topsort():
    print(*q[:tt+1])
else:
    print(-1)

最短路

单源最短路——Dijkstra——非负权图(基于贪心)

朴素Dijkstra($O(n^2)$)——稠密图

def add(a,b,c):
    global idx
    e[idx]=b
    w[idx]=c
    ne[idx]=head[a]
    head[a]=idx
    idx+=1

def dijkstra():
    dist[1]=0
    for i in range(n-1):
        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
        for j in range(1,n+1):
            dist[j]=min(dist[j],dist[t]+g[t][j])
    if dist[n]==float('inf'):
        return -1
    return dist[n]

n,m=map(int,input().split())
N=n+10
g=[[float('inf')]*N for i in range(N)]
dist=[float('inf')]*N;st=[False]*N
for i in range(1,n+1):
    g[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    g[a][b]=min(g[a][b],c)

print(dijkstra())

堆优化Dijkstra($O(mlog_2n)$)——稀疏图

from heapq import heapify,heappush,heappop
def add(a,b,c):
    global idx
    e[idx]=b
    w[idx]=c
    ne[idx]=head[a]
    head[a]=idx
    idx+=1

def dijkstra():
    q=[]
    heapify(q)
    dist[1]=0
    heappush(q,(dist[1],1))
    while q:
        distance,ver=heappop(q)
        if st[ver]:
            continue
        st[ver]=True
        i=head[ver]
        while i!=-1:
            j=e[i]
            if dist[j]>distance+w[i]:
                dist[j]=distance+w[i]
                heappush(q,(dist[j],j))
            i=ne[i]
    if dist[n]==float('inf'):
        return -1
    return dist[n]

n,m=map(int,input().split())
N=n+10;M=m+10
e=[0]*M;ne=[0]*M;head=[-1]*M;idx=0;w=[0]*M
dist=[float('inf')]*N;st=[False]*N
for i in range(m):
    a,b,c=map(int,input().split())
    add(a,b,c)

print(dijkstra())

单源最短路——有负权边(基于迭代)

bellman_ford($O(nm)$) —— 有边数限制的最短路只能用bellman_ford

def bellman_ford():
    dist[1]=0
    for i in range(k):
        backup=dist.copy()
        for j in range(m):
            a,b,c=edge[j]
            dist[b]=min(dist[b],backup[a]+c)
    if dist[n]==float('inf'):
        return 'impossible'
    return dist[n]

n,m,k=map(int,input().split())
N=n+10;M=m+10
edge=[(0,0,0)]*M;dist=[float('inf')]*N
for i in range(m):
    a,b,c=map(int,input().split())
    edge[i]=(a,b,c)
print(bellman_ford())

spfa($O(m)$)——特殊图上可能退化成($O(nm)$)

from collections import deque
def add(a,b,c):
    global idx
    e[idx]=b
    w[idx]=c
    ne[idx]=head[a]
    head[a]=idx
    idx+=1

def spfa():
    q=deque()
    dist[1]=0
    q.append(1)
    st[1]=True
    while q:
        t=q.popleft()
        st[t]=False
        i=head[t]
        while i!=-1:
            j=e[i]
            if dist[j]>dist[t]+w[i]:
                dist[j]=dist[t]+w[i]
                if not st[j]:
                    q.append(j)
                    st[j]=True
            i=ne[i]
    if dist[n]==float('inf'):
        return 'impossible'
    return dist[n]

n,m=map(int,input().split())
N=n+10;M=m+10
e=[0]*M;ne=[0]*M;head=[-1]*N;idx=0;w=[0]*M
dist=[float('inf')]*N;st=[False]*N

for i in range(m):
    a,b,c=map(int,input().split())
    add(a,b,c)

print(spfa())

spfa判负环

from collections import deque
def add(a,b,c):
    global idx
    e[idx]=b
    w[idx]=c
    ne[idx]=head[a]
    head[a]=idx
    idx+=1

def spfa():
    q=deque()
    for i in range(1,n+1):
        q.append(i)
        dist[i]=0
        st[i]=True
    while q:
        t=q.popleft()
        st[t]=False
        i=head[t]
        while i!=-1:
            j=e[i]
            if dist[j]>dist[t]+w[i]:
                dist[j]=dist[t]+w[i]
                cnt[j]=cnt[t]+1
                if cnt[j]>=n:
                    return True
                if not st[j]:
                    q.append(j)
                    st[j]=True
            i=ne[i]
    return False

n,m=map(int,input().split())
N=n+10;M=m+10
e=[0]*M;ne=[0]*M;head=[-1]*N;w=[float('inf')]*M;idx=0
dist=[float('inf')]*N;st=[False]*N;cnt=[0]*N
for i in range(m):
    a,b,c=map(int,input().split())
    add(a,b,c)
if spfa():
    print('Yes')
else:
    print('No')

多源汇最短路

floyd

def floyd():
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                g[i][j]=min(g[i][j],g[i][k]+g[k][j])

n,m,k=map(int,input().split())
N=n+10
g=[[float('inf')]*N for i in range(N)]
dist=[float('inf')]*N
for i in range(1,n+1):
    g[i][i]=0
for i in range(m):
    x,y,z=map(int,input().split())
    g[x][y]=min(g[x][y],z)
floyd()
for i in range(k):
    x,y=map(int,input().split())
    if g[x][y]==float('inf'):
        print('impossible')
    else:
        print(g[x][y])

最小生成树

定理：任意一棵最小生成树一定包含无向图中权值最小的边

朴素版Prim算法 ($O(n^2)$)(稠密图)

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
        if i and dist[t]==float('inf'): #如果最近的点与连通块不连通，则不存在最小生成树
            return 'impossible'
        if i:                           #res+此点与连通块的距离
            res+=dist[t]
        st[t]=True                      #放入连通块
        for j in range(1,n+1):          #更新所有点与连通块的距离
            dist[j]=min(dist[j],g[t][j])
    return res

n,m=map(int,input().split())
N=n+10
g=[[float('inf')]*N for i in range(N)]
dist=[float('inf')]*N;st=[False]*N
for i in range(m):
    a,b,c=map(int,input().split())
    g[a][b]=g[b][a]=min(g[a][b],c)
print(prim())

堆优化Prim算法($O(mlog_2n)$)(稀疏图)

没讲，不会

Kruskal 算法($O(mlog_2m)$)(稀疏图)

def kruskal():                  #维护无向图的最小生成森林         
    res=0
    cnt=0
    for i in range(m):          #枚举每条边
        a,b,c=edges[i]
        pa=find(a);pb=find(b)
        if pa!=pb:              #若两座森林不连通，则使其连通
            p[pa]=pb
            res+=c
            cnt+=1
    if cnt<n-1:
        return  'impossible'
    return res

def find(x):
    if p[x]!=x:
        p[x]=find(p[x])
    return p[x]

n,m=map(int,input().split())
N=n+10
p=[0]*N
for i in range(1,n+1):          #每棵树最初自己是一座森林
    p[i]=i
edges=[]
for i in range(m):
    a,b,c=map(int,input().split())
    edges.append((a,b,c))
edges.sort(key=lambda x:x[2])   #按权重排序
print(kruskal())

次小生成树

def find(x):
    if p[x]!=x:
        p[x]=find(p[x])
    return p[x]

def add(a,b,c):
    global idx
    e[idx]=b
    w[idx]=c
    ne[idx]=head[a]
    head[a]=idx
    idx+=1

def kruskal():
    res=0
    for i in range(m):
        a,b,c,f=edges[i]
        pa=find(a);pb=find(b)
        if pa!=pb:
            p[pa]=pb
            add(a,b,c);add(b,a,c)
            edges[i][3]=True
            res+=c
    return res

def dfs(u,fa,maxd1,maxd2,d1,d2):
    d1[u]=maxd1;d2[u]=maxd2
    i=head[u]
    while i!=-1:
        j=e[i]
        if j!=fa:
            td1=maxd1;td2=maxd2
            if w[i]>td1:
                td2=td1;td1=w[i]
            elif td1>w[i]>td2:
                td2=w[i]
            dfs(j,u,td1,td2,d1,d2)
        i=ne[i]
    return

n,m=map(int,input().split())
N=n+10
p=[0]*N
e=[0]*N*2;ne=[0]*N*2;head=[-1]*N;w=[0]*N*2;idx=0
dist1=[[0]*N for i in range(N)]
dist2=[[0]*N for i in range(N)]
for i in range(1,n+1):
    p[i]=i
edges=[]
for i in range(m):
    a,b,c=map(int,input().split())
    edges.append([a,b,c,False])
edges.sort(key=lambda x:x[2])
suma=kruskal()                                              #求最小生成树
for i in range(1,n+1):
    dfs(i,-1,-float('inf'),-float('inf'),dist1[i],dist2[i]) #求树上任意两点间的最大边和次大边
res=float('inf')
for i in range(m):
    a,b,c,f=edges[i]
    if not f:                                               #用非树边替换树边，得次小生成树
        if c>dist1[a][b]:                                   #替换最大边
            t=suma+c-dist1[a][b]
        elif c>dist2[a][b]:                                 #若最大边替换后和原来一样，则替换次大边
            t=suma+c-dist2[a][b]
        res=min(res,t)
print(res)

差分约束

最近公共祖先(LCA)