python算法复习笔记3(拓扑序，Dijkstra，SPFA，最小生成树，LCA，二分图)

题目来源：https://www.acwing.com/activity/content/2869/

有向图的拓扑序列

题意

给定一个n个点m条边的有向图，点的编号是 1到n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

思路

拓扑序列模板，属于bfs的应用

• 首先记录各个点的入度

• 然后将入度为 0 的点放入队列

• 将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同事边的另一侧的点的入度 -1。

• 如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。

代码

from sys import stdin
from collections import deque

(n,m) = map(int,stdin.readline().strip().split(' '))
mp = [[] for i in range(n+5)]
d = [0 for i in range(n+5)]
ans = []
qu = deque()

for i in range(m):
    (x,y) = map(int,stdin.readline().strip().split(' '))
    mp[x].append(y)
    d[y]+=1

for i in range(1,n+1):
    if d[i]==0:
        qu.append(i)

while len(qu):
    tp = qu.popleft()
    ans.append(tp)
    for nx in mp[tp]:
        d[nx]-=1
        if d[nx]==0:
            qu.append(nx)
            
if len(ans)==n:
    for i in ans:
        print(i,end=' ')
else:
    print("-1")

构造有向无环图

题意

给定一个由n个点和m条边构成的图。不保证给定的图是连通的。
图中的一部分边的方向已经确定，你不能改变它们的方向。
剩下的边还未确定方向，你需要为每一条还未确定方向的边指定方向。
你需要保证在确定所有边的方向后，生成的图是一个有向无环图（即所有边都是有向的且没有有向环的图）。

2≤n≤2×10e5  1≤m≤min(2×10e5,n(n−1)/2)

思路

是有向无环图的充要条件是存在拓扑序

• 如果有向边已经构成环了，无解
• 如果有向边未构成环，将无向边的顺序定义为拓扑序，必定有解。（这就是选择方向的策略）

代码

from sys import stdin
from collections import deque

t = int(stdin.readline().strip())
for _ in range(t):
    (n,m) = map(int,stdin.readline().strip().split(' '))
    qu = deque()
    mp = [[] for i in range(n+2)]
    li = []
    d = [0 for i in range(n+2)]
    topxu = [0 for i in range(n+2)]
    cnt = 0

    for i in range(m):
        (t,x,y) = map(int,stdin.readline().strip().split(' '))
        li.append((x,y,t))
        if t==1:
            mp[x].append(y)
            d[y]+=1

    for i in range(1,n+1):
        if d[i]==0:
            qu.append(i)
            
    while len(qu):
        tp = qu.popleft()
        cnt+=1
        topxu[tp] = cnt
        for nx in mp[tp]:
            d[nx]-=1
            if d[nx]==0:
                qu.append(nx)
    if cnt==n :
        print("YES")
        for v in li:
            if v[2]==0:
                if topxu[v[0]] > topxu[v[1]]:
                    print(v[1],v[0])
                else:
                    print(v[0],v[1])
            else:
                print(v[0],v[1])
        
    else :print("NO")

最短距离

题意

给定n个点m条有向边的连通图。

其中有K个商店。

给出Q个询问，第i个询问给出yi，问该村庄距离最近的商店有多远。

思路

• DijKstra的核心思想是贪心。不能用于负权边
• 先将起点距离自己的距离设为0，其余设为正无穷。
• 每次找到目前没有被找到过并且距离起点最近的点。再用这个点更新其他点的距离
• st 存储每个点的最短路是否已经确定

把K个商店看成起点，求一次最短路即可

具体的做法是建一个虚拟源点，到K个商店的距离为0。

用heapq实现优先队列，只能实现小根堆，最大堆只能对元素取反

• heapq.heappush(heap, item)

  将 item 的值加入 heap 中，保持堆的不变性。

• heapq.heappop(heap)

  弹出并返回 heap 的最小的元素，保持堆的不变性。使用 heap[0] ，可以只访问最小的元素而不弹出它。

• heapq.heapify(x)

  将list x 转换成堆，原地，线性时间内。

代码

from sys import stdin
from collections import deque
import heapq


(N,M) = map(int,stdin.readline().strip().split(' '))
mp = [[] for i in range(N+5)]

for i in range(M):
    (a,b,c) = map(int,stdin.readline().strip().split(' '))
    mp[a].append([c,b])
    mp[b].append([c,a])

K = int(stdin.readline().strip())
sd = []

for i in range(K):
    x = int(stdin.readline().strip())
    mp[N+1].append([0,x])


st = [False for i in range(N+5)] # 是否已更新
dis = [2000000000 for i in range(N+5)]

qu = [[0,N+1]]
dis[N+1] = 0

while len(qu):
    tp = heapq.heappop(qu)
    d,nw = tp[0],tp[1] 
    if st[nw]:continue
    st[nw]=True
    
    for nx in mp[nw]:
        if nx[0]+dis[nw] < dis[nx[1]]:
            dis[nx[1]] = nx[0]+dis[nw]
            heapq.heappush(qu,[dis[nx[1]],nx[1]])

Q = int(stdin.readline().strip())
for i in range(Q):
    a = int(stdin.readline().strip())
    print(dis[a])

作物杂交

题意

https://www.acwing.com/problem/content/3308/

N种作物，每种作物对应一个成熟时间

作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。

初始拥有其中 M种作物的种子 (数量无限，可以支持多次杂交)。

一堆杂交方案K

目标种子 T

思路

SPFA

• 思路是DP，可以处理负权边与负权回路。
• 松弛函数：dis[v] > dis[u] + g[u][v]则更新
• 先将起点距离自己的距离设为0，其余设为正无穷。
• st 存储该点是否在队列中，队列只用存点的标号
• 将前导节点松弛成功过的节点放在队列中，每次取出一个元素进行松弛操作，直到队中没有元素。

这道题准确来说是最短路优化的DP。直接套SPFS就行了

代码

from sys import stdin
from collections import deque
import heapq

N,M,K,T = map(int,stdin.readline().strip().split(" "))

qu = []
dis = [2000000000 for i in range(N+5)]
st = [False for i in range(N+5)]
mp = [[] for i in range(N+5)] # 杂交方案mp[a] = [b,c] 表示 a+b->c

t = list(map(int,stdin.readline().strip().split(" ")))
t = [0]+t
k = list(map(int,stdin.readline().strip().split(" ")))

for i in k:
    heapq.heappush(qu,i)
    dis[i] = 0
    st[i] = True

for _ in range(K):
    A,B,C = map(int,stdin.readline().strip().split(" "))
    mp[A].append((B,C))
    mp[B].append((A,C))

def spfa():
    while len(qu):
        a = heapq.heappop(qu)
        st[a] = False
        for plan in mp[a]:
            b,c= plan[0],plan[1]
            if dis[c] > max(dis[a],dis[b])+max(t[a],t[b]):
                dis[c] = max(dis[a],dis[b])+max(t[a],t[b])
                if st[c]==False:
                    heapq.heappush(qu,c)
                    st[c] = True
        
spfa()
print(dis[T])

单词环

题意

https://www.acwing.com/problem/content/1167/

思路

建图

一个比较直观的建图方式是将每个单词作为一个节点,如果这两个单词能够相连,则在这两个单词之间连接一条有向边,此时最多有10e5个点，10e10条边。不能接受。

考虑一个对偶的建图方式,将每一个单词看作一条边,其开头两个字符和结尾两个字符为它两边的点。这样建图的话,节点数就缩小到了26*26，边数为10e5条。

0/1分数规划

我们所要求的答案为$\sum{len}/s$的最大值。可以发现问题具有单调性，可以用二分解决。

设左端点为l,右端点为r,中点为mid。当$\sum{len}/s$ > mid时，$\sum{len}-s*mid > 0$，则可以将图中的边权设成len[i] - mid

原问题可以转化为求当前图中有无正环.

优化

在用SPFA求正环的过程中,可以采取一种比较取巧的方法:当求最长路时,经过的点大于某一个数时,我们就可以武断地认为当前图中存在一个正环.

代码

from sys import stdin
from collections import deque
import heapq

def check(mid):
    q=deque([i for i in range(1,idx)])
    st=[True]*idx
    dis=[0]*idx
    cnt=[0]*idx
    count=0
    while q:
        cur=q.popleft()
        st[cur]=False
        if cur in graph:
            for nx in graph[cur]:
                if dis[nx]<dis[cur]+graph[cur][nx]-mid:
                    dis[nx]=dis[cur]+graph[cur][nx]-mid
                    cnt[nx]=cnt[cur]+1
                    count+=1
                    if count>2000:
                        return True
                    if cnt[nx]>=idx-1:
                        return True
                    if not st[nx]:
                        st[nx]=True
                        q.append(nx)

    return False

while True:
    n = int(input())
    if n==0:break
    graph = {}
    dic = {}
    idx = 1
    for _ in range(n):
        s=input()
        a=s[:2]
        b=s[-2:]
        l=len(s)

        if a not in dic:
            dic[a]=idx
            idx+=1

        if b not in dic:
            dic[b]=idx
            idx+=1
        a =  dic[a]
        b = dic[b]
        if a not in graph:
            graph[a]={}

        graph[a][b]=max(graph[a].get(b,0),l)

    if not check(0):
        print("No solution")
    else:
        left=0
        r=1000
        while r-left>10**-4:
            mid=(left+r)/2
            if check(mid):
                left=mid
            else:
                r=mid
        print(r)

城市通电

题意

最小生成树模板题

思路

排序方法

1 关键字 key

key = lambda x:x[2] 返回第二个元素作为排序依据

a = [(1, 3, 5), (2, 2, 2), (4, 7, 8), (10, 8, 1), (3, 8, 1)]
a.sort(key=lambda x:x[2])
print(a)

2 自定义函数

import functools

key = functools.cmp_to_key(mycomp)

import functools

def mycomp(x, y):
    if x[2] == y[2]:
        if x[1] == y[1]:
            return x[0] - y[0]
        else:
            return x[1] - y[1]
    else:
        return x[2] - y[2]


a = [(1, 3, 5), (2, 2, 2), (4, 7, 8), (10, 8, 1), (3, 8, 1)]
a.sort(key=functools.cmp_to_key(mycomp))
print(a)

代码

from sys import stdin
from collections import deque
import heapq
import functools

n = int(stdin.readline().strip())
X = [0 for i in range(n+5)]
Y = [0 for i in range(n+5)]
faa = [i for i in range(n+5)]
edge = []

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


for i in range(1,n+1):
    x,y = map(int,stdin.readline().strip().split())
    X[i],Y[i]=x,y


C = list(map(int,stdin.readline().strip().split()))
C = [0]+C


# 虚拟源点编号0
for i in range(1,n+1):
    edge.append((C[i],0,i))

K = list(map(int,stdin.readline().strip().split()))
K = [0]+K

for i in range(1,n):
    for j in range(i+1,n+1):
        le = abs(X[i]-X[j]) + abs(Y[i]-Y[j])
        edge.append((le*(K[i]+K[j]),i,j))

edge.sort(key = lambda x:x[0])

# 建立最小生成树
cost,v,idx,e = 0,0,0,0
liv = []
lie = []

for _ in range(n):
    while True:
        ed = edge[idx]
        idx += 1
        cc ,aa,bb =ed[0],ed[1],ed[2]
        fa,fb = find(aa),find(bb)
        if fa!=fb:
            faa[fa] = faa[fb]
            cost+=ed[0]
            if aa==0:
                v+=1
                liv.append(bb)
            else:
                e+=1
                lie.append((aa,bb))
            break

print(cost)
print(v)
for i in liv:
    print(i,end='')
    if i!=liv[-1]:
        print(' ',end='')
    else: print()
print(e)
for i in lie:
    print(i[0],i[1])

二叉树

题意

给定一个n个结点（编号 1∼n）构成的二叉树，其根结点为 1号点。
进行m次询问，每次询问两个结点之间的最短路径长度。
树中所有边长均为1。
n,m<1000

思路

一次dfs确定最近每个点到根节点的距离d[i]。

i , j之间的距离是d[i]+d[j]-2d[p] p是i j的最近公共祖先

数据量小，不需要倍增，暴力求公共祖先即可，爬山法：

• 先把较低的点爬到相同的高度
• 再同时向上爬，直到相遇

具体的代码，同时维护每个点的子节点，和父结点即可

代码

from sys import stdin
from collections import deque
import heapq
import functools

T = int(stdin.readline().strip())

def dfs(u,depth):
    global l,r,d
    d[u]=depth
    if l[u]!=-1:dfs(l[u],depth+1)
    if r[u]!=-1:dfs(r[u],depth+1)

def lca(x,y):
    global p,d

    if d[x] < d[y]: x,y = y,x
    while d[x] > d[y]:
        x = p[x]
        
    while x!=y : x,y = p[x],p[y]
    return x

for _ in range(T):
    n,m = map(int,stdin.readline().strip().split(' '))
    p = [0 for i in range(n+5)]
    l = [-1 for i in range(n+5)]
    r = [-1 for i in range(n+5)]
    d = [-1 for i in range(n+5)]
    for i in range(1,n+1):
        x,y = map(int,stdin.readline().strip().split(' '))
        l[i]=x
        r[i]=y
        if x!=-1: p[x]=i
        if y!=-1: p[y]=i
    dfs(1,0)
    for i in range(m):
        x,y = map(int,stdin.readline().strip().split(' '))
        fa = lca(x,y)
        print(d[x]+d[y]-2*d[fa])

祖孙询问

题意

裸题

思路

倍增LCA，和st表一样

• fa[i][j]表示从i开始，向上走 2^j 步后的节点编号
  • j=0时fa[i][0]=p[i]
  • j>0时fa[i][j] = f[f[i][j-1]][j-1]
  • 哨兵：如果跳过了规定fa[i,j]=0，dis[0]=0
• depth[i]表示深度
• 求最近公共祖先分两步来做
  • 先将两个点跳到同一层，基于一个二进制拼凑的思想，从大往小枚举
  • 同样的思想，跳到LCA的下一层（考虑到f[a][k]=f[b][k]只能说明在LCA或者它的上面）

代码

from sys import stdin
from collections import deque
import heapq
import functools


fa = [[0 for j in range(18)] for i in range(40010)]
deep = [99999 for i in range(40010)]
root = 0
mp = [[] for i in range(40010)]

n = int(stdin.readline().strip())

def bfs():
    global root,deep,mp,fa
    qu = deque()
    deep[0]=0
    deep[root] = 1 
    qu.append(root)
    while len(qu):
        tp = qu.popleft()
        for nx in mp[tp]:
            if deep[nx]> deep[tp]+1:
                deep[nx] = deep[tp]+1
                fa[nx][0] = tp
                for i in range(1,17):
                    fa[nx][i] = fa[fa[nx][i-1]][i-1]
                qu.append(nx)
                
def lca(x,y):
    if deep[x] < deep[y]:x,y = y,x
    for i in range(16,-1,-1):
        if deep[fa[x][i]] >= deep[y]:
            x = fa[x][i]

    if x==y:return x
    
    for i in range(16,-1,-1):
        if deep[fa[x][i]] != deep[fa[y][i]]:
            x,y = fa[x][i],fa[y][i]

    return fa[x][0]
    
for i in range(n):
    a,b = map(int,stdin.readline().strip().split())
    mp[a].append(b)
    if b==-1:root = a
    else: mp[b].append(a)

m = int(stdin.readline().strip())

bfs()
for i in range(m):
    x,y = map(int,stdin.readline().strip().split())
    pp = lca(x,y)
    if pp==x: print(1)
    elif pp==y:print(2)
    else:print(0)

完美牛棚

题意

给一个二分图，求最大匹配

思路

匈牙利算法 n*3

代码