ICPC python模板汇总(用于打印)

Chuanhua Yu 发布于

最后更新于

[TOC]

ICPC python模板汇总(用于打印-偏图论)

Fast Input/Output

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
# Created by iN_siDious.
# Copyright © 2024 iN_siDious. All rights reserved.
import sys,os
import random
from math import inf,ceil,sqrt
from string import ascii_lowercase,ascii_uppercase
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import heappushpop, heapify, heappop, heappush
from bisect import bisect_left,bisect_right
from types import GeneratorType
from random import randint
RANDOM = randint(1, 10 ** 10)
class op(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(op, self).__hash__() ^ RANDOM
# --------------------
# 手写栈模板
# 克服py栈太浅的问题
# 注意要用yield 不要用return
# 函数结尾要写yield None
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
input = lambda: sys.stdin.buffer.readline().decode().strip()
out=sys.stdout.write
def S():
    return input()
def I():
    return int(input())
def MI():
    return map(int, input().split())
def MF():
    return map(float, input().split())
def MS():
    return input().split()
def LS():
    return list(input().split())
def LI():
    return list(map(int,input().split()))
def print1(x):
    return out(str(x)+"\n")
def print2(x,y):
    return out(str(x)+" "+str(y)+"\n")
def print3(x,y,z):
    return out(str(x)+" "+str(y)+" "+str(z)+"\n")
def Query(i,j):
    print3('?', i, j)
    sys.stdout.flush()
    qi=I()
    return qi
def print_arr(arr):
    out(' '.join(map(str,arr)))
    out(str("\n"))

# ----------------------------- # ----------------------------- #

字符串python模板

​ 如果字符串 的同长度的前后缀完全相同，即 则称此前缀(后缀)为一个 ，根据语境，有时 也指长度。特殊的，字符串本身也可是其本身的 具体看语境。

周期和循环节

​ 对于字符串 和正整数 ，如果 ，对于 成立，则称 为 的一个周期。特别的， 一定是 的一个周期。

​ 若字符串 的周期 满足 ，则称 为 的一个循环节。特别的， 一定是 的一个循环节。

性质

  • 是的周期是的一个 。因此，字符串的周期性质等价于 性质，求周期也等价于求 。( 不具有二分性)
  • 的的也是的，求 的所有 等价于求所有前缀的最大

算法

数组和 数组的预处理

的非平凡的最大

  1. 初始化
  2. 不断尝试扩展匹配长度 ，如果扩展失败（下一个字符不相等），令 变为 ，直至 为 （应该重新开始从头开始匹配）。
  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
class Kmp:
    def __init__(self, t):
        """字符串从 1 开始
        t:模式串
        s:原字符串
        """
        n = len(t)
        nxt = [0] * n

        for i in range(2, n):  # 预处理next数组
            nxt[i] = nxt[i - 1]
            while nxt[i] and t[i] != t[nxt[i] + 1]:
                nxt[i] = nxt[nxt[i]]
            nxt[i] += 1 if t[i] == t[nxt[i] + 1] else 0

        self.nxt = nxt

    def get_f(self, t, s):
        nxt = self.nxt,len(s)
        n,m = len(nxt),len(s)
        f = [0]*m
        j = nxt[1]
        for i in range(1, m + 1):  # 预处理f数组
            while j and (j == n or t[i] != s[j + 1]): j = nxt[j]
            if t[i] == s[j + 1]: j += 1
            f[i] = j
            # if f[i] == n: (t 在 s 中某一次出现)
        return f

数据结构python模板

树状数组

局限性

树状数组被理解成是“可以修改”的前缀和。使用时的局限性：

  1. 因为树状数组的本质是前缀和，所以依赖“前缀可减性”
  2. 树状数组的单点修改具有局限性，例如“带修改的前缀max,min”问题中，修改必须具有单调性。

1.lowbit

1
2
def lowbit(x) -> int:
    return x&-x

2.查询

1
2
3
4
5
6
7
su = [0] * 100005
def query(pos) -> int:
    res = 0
    while pos:
        res += su[pos]
        pos -= lowbit(pos)
    return res

3.修改

1
2
3
4
5
su = [0] * 100005
def change(pos, x) -> None:
    while pos <= n:
        su[pos] += x
        pos += lowbit(pos)

线段树

以维护区间最小值为例

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
import sys
input = sys.stdin.readline
# py可能会超时
class tnode:
    def __init__(self):
        self.min = 0
        self.lazy = 0
        self.l = 0
        self.r = 0

class SegmentTree:
    def __init__(self, n:int) -> None:
        self.t = [tnode() for _ in range(4 * (n+1))]

    def pushdown(self, root:int) -> None:
        """懒标记下传合并, 根据题目要求设计"""
        if self.t[root].lazy != 0:
            self.t[root].min += self.t[root].lazy
            if self.t[root].l != self.t[root].r:
                ch = root << 1
                self.t[ch].lazy += self.t[root].lazy
                self.t[ch+1].lazy += self.t[root].lazy
            self.t[root].lazy = 0

    def update(self, root:int) -> None:
        """ 区间合并，根据维护的数据变动"""
        ch = root << 1
        self.pushdown(ch)
        self.pushdown(ch+1)
        self.t[root].min = min(self.t[ch].min, self.t[ch+1].min)

    def build(self, root:int, l:int, r:int, ls:list) -> None:
        """递归建树"""
        self.t[root].l = l
        self.t[root].r = r
        self.t[root].lazy = 0
        if l != r:
            mid = (l+r)>>1  # 注C++这么写可能会爆 int，建议参考oi-wiki
            ch = root<<1
            self.build(ch, l, mid, ls)
            self.build(ch+1, mid+1, r, ls)
            self.update(root)
        else:
            self.t[root].min = ls[l]
            # self.mp[l] = root

    def change(self, root:int, l:int, r:int, delta:int) -> None:
        """ 作用: 区间修改 """
        self.pushdown(root)
        if l == self.t[root].l and r == self.t[root].r:
            self.t[root].lazy += delta
            return
        mid = (self.t[root].l+self.t[root].r)>>1
        ch = root<<1
        if r <= mid: self.change(ch,l,r,delta)
        elif l > mid: self.change(ch+1,l,r,delta)
        else:
            self.change(ch,l,mid,delta)
            self.change(ch+1,mid+1,r,delta)
        self.update(root)

    def query_min(self, root:int, l:int, r:int) -> int:
        self.pushdown(root)
        if self.t[root].l == l and self.t[root].r == r:
            return self.t[root].min
        mid = (self.t[root].l+self.t[root].r) >> 1
        ch = root<<1
        if r <= mid: return self.query_min(ch,l,r)
        elif l > mid: return self.query_min(ch+1,l,r)
        else: return min(self.query_min(ch,l,mid),self.query_min(ch+1,mid+1,r))

数学python模板

快速幂

1
2
3
4
5
6
7
8
9
10
11
p = 998244353
def fastpow(a, n):
    base, res = a, 1
    while n != 0:
        if n & 1: #取最后一位二进制数，看是否为1
            res = res * base % p
        base = base * base % p
        n >>= 1
    return res%p
"""自带的快速幂"""
pow(a,b,p) # a^b mod p

第二类斯特林数

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
class Factorial:
    def __init__(self, N, mod) -> None:
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod
 
    def comb(self, n, m):
        if n < 0 or m < 0 or n < m:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod
 
    def perm(self, n, m):
        if n < 0 or m < 0 or n < m:
            return 0
        return self.f[n] * self.g[n - m] % self.mod
 
    def catalan(self, n):
        # TODO: check 2 * n < N#
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod
 
    # N个不同的物品放进m个不同的集合，保证每个集合都不是空集#
    def sterling(self, n, m):
        if n < m:
            return 0
        else:
            res = 0
            for i in range(m + 1):
                t = self.comb(m, i) * pow(m - i, n, self.mod) % self.mod
                if i & 1:
                    res -= t
                else:
                    res += t
                res %= self.mod
            return res * self.g[m] % self.mod
         
n,m = map(int,input().split())
t = Factorial(n+1,int(1e9) + 7)
print(t.sterling(n,m))

1、质数

从 到 中有 个质数

(1) 判定（试除法）

1
2
3
4
5
6
def is_primer(n):
	i = 2
    while i <= n // i:
        if n % i == 0: return False
        i += 1
    return True

(2)分解质因数（试除法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
primes,c = [],[]
def divide(n):
    i = 2
    while i*i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                cnt += 1
            primes.append(i)    # i 为质因数，cnt 为对应的指数
            c.append(cnt)
        i += 1
    if n > 1:
        primes.append(n)
        c.append(1)

如果有多次询问：当然可以预处理质数O(sqrt(n)),每次询问O(sqrt(n)/log(n))

(3)埃氏筛法 

1
2
3
4
5
6
7
ls, primes = [0]*(n+1), []
def get_primes(n):
    for i in range(2, int(sqrt(n))+1):
        if not ls[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                ls[j] = 1

(4)埃氏筛变形：区间筛

对于给定区间 ，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
MAXN = 46400  #sqrt(2147483647)
prime = []
is_prime = [1] * MAXN

for i in range(2, MAXN):
    if is_prime[i]:
        prime.append(i)
        for j in range(i*i, MAXN, i):
            is_prime[j] = 0
def solve():
    l, r = map(int, sys.stdin.readline().split())
    if l == 1: l += 1  #不处理的话,1会筛不掉
    n = r - l + 1
    if n < 2: return
    vis = [0] * n
    for p in prime:
        if p > r: break
        for i in range((l+p-1)//p * p, r//p*p+1, p):
            if i == p: continue
            vis[i-l] = 1
    ls = []
    for i in range(n):
        if vis[i]: continue
        ls.append(i)

(5)线性筛法（确保了每个被筛掉的合数都是由其最小质因子筛掉的）

当 时，由于我们是从小到大遍历质数，所以 是 的最小质因子，也是 的最小质因子。

当 时， 小于 的最小质因子，所以也是 的最小质因子。

1
2
3
4
5
6
7
8
9
10
N = 3*10**5
is_prime = [1]*(N+1)
primes = []
for i in range(2,N+1):
    if is_prime[i]: primes.append(i)
    j = 0
    while primes[j] <= N//i:
        is_prime[primes[j]*i] = 0
        if i % primes[j] == 0: break
        j += 1

2、约数

(1)扩展欧几里得算法

所以：

又 $a \mod b = a - a//bb所以推导得：ax + by = b(x’ - a//by’) + ay’ = d$

即：

1
2
3
4
def exgcd(a, b):
    if b == 0: return [a, 1, 0]
    [g, x, y] = exgcd(b, a % b)
    return [g, y, x - a // b * y]

ex_gcd解方程技巧

假设 ax+by = (a,b) 的一组解为，则通解为：，

有解当且仅当 ，特解为

假设要解方程 ，只要 互为质数，那么解出来 后再乘个 就是上述方程的解

3、同余与模

  • 判定在 里 a 是否有逆元
  • 如果有如何求解逆元

考虑 有解，当且仅当 互质，如果 为质数，则 ~ 在模 的情况下有逆。

欧拉定理

如果 ，那么 ，其中 是欧拉函数。

费马小定理

乘法逆元的三种求法

  • 扩展欧几里得算法：，已知 求
  • 欧拉定理：设 为正整数， 且 ，
  • 费马小定理：当模数 为质数时 即为 的乘法逆元

求 ~ （对于质数 的逆元）：

1
2
3
4
inv = [0]*(n+1)
inv[1] = 1
for i in range(2,n+1):
    inv[i] = (-inv[p%i]*(p//i)) % p

解同余方程组

我们可以通过一次扩展欧几里得将 个同余方程转化为 个同余方程。

及可通过 次扩欧将 $\begin{equation}
\left\{
\begin{aligned}
x≡a_1\mod m_1\
x≡a_2\mod m_2\
.~~~~~.\
.~~~~~.\
.~~~~~~~.\
x≡a_k\mod m_k
\end{aligned}
\right.
\end{equation}转化为x≡x_0 \mod [m_1,m_2,…,m_k]$。

同余方程组的构造解(孙子定理、中国剩余定理)

如果 是 个凉凉互质的正整数，则同余方程组$\begin{equation}
\left\{
\begin{aligned}
x≡a_1\mod m_1\
x≡a_2\mod m_2\
.~~~~~.\
.~~~~~.\
.~~~~~~~.\
x≡a_k\mod m_k
\end{aligned}
\right.
\end{equation}的解为x≡\sum_{i=1}^kM_i’M_ia_i\mod M$

其中

4、简单排列与组合

基础：加法原理和乘法原理

阶乘

1
2
from math import factorial
factorial(n)   # 返回 n!

5、树与图上的计数问题

各类计数问题的常用方法

  1. 直接计算
  2. DP(递推)
  3. 容斥
  4. 生成函数

6、概率与期望

图论基础算法python模板

链式前向星

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 = [0]*(n+1)
ver,edge,nxt = [0]*(2*m+1),[0]*(2*m+1),[0]*(2*m+1)
tot = 1   #为异或求反向边做铺垫

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}')

树上问题维护及Tarjan与图的连通性

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
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_))

2、LCA与树链剖分

倍增法求 

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
import sys
from collections import deque
input = sys.stdin.readline

def bfs(r) -> None:
    """bfs里套了个DP,在nlogn的时间里预处理了基于倍增的向上标记"""
    d[r] = 1
    q = deque()
    q.append(r)
    while q:
        x = q.popleft()
        for y,w in g[x]:
            if not d[y]:
                d[y] = d[x] + 1
                f[y][0] = x
                q.append(y)
            for k in range(1,20):
                f[y][k] = f[f[y][k-1]][k-1]

def lca(x,y) -> int:
    if d[x] < d[y]: x,y = y,x
    for i in range(19,-1,-1):
        if d[f[x][i]] >= d[y]: x = f[x][i]
    if x == y: return y
    for i in range(19,-1,-1):
        if f[x][i] != f[y][i]: x,y = f[x][i],f[y][i]
    return f[x][0]

n,m = map(int,input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    x,y,z = map(int,input().split())
    g[x].append((y,z))
    g[y].append((x,z))

d = [0]*(n+1)  # 点的深度，根为1，0表示还未计算
f = [[0]*20 for _ in range(n+1)]   # pow(2,20) > 1000000
bfs(1)    # bfs里套了个DP,在 nlogn 的时间里预处理了基于倍增的向上标记

q = int(input())  # q次询问
for _ in range(q):
    x,y = map(int,input().split())
    print(lca(x,y))

求

待更新

3、算法与无向图连通性

  • 关于 和 缩点的应用可能结合倍增 算法，多次回答无向图上两点之间的必经边、必经点的询问。

时间戳

在图的深度优先遍历中，按照每个结点第一次被访问的顺序，依次给予 个结点 ~ 的整数标记，该标记就被称为“时间戳”，记为 。

搜索树

在无向连通图中任选一个结点进行 ，每个结点只访问一次。所有发生递归的边 构成一棵树，我们把它称为“无向连通图的搜索树”。一般的无向连通图的各个连通块的搜索树构成无向图的搜索森林。

追溯值

返祖边：搜索树上的一个点连向其祖先结点的边

横插边：搜索树上一个点连向它另一条支链上的点的边（只存在于有向图）

定义为当前点及其子树的仅通过一条返祖边能连到 值最小的点

是树边:

是返祖边:

什么样的点是割点？

  1. 有多个儿子的根结点。
  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
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
# Created by iN_siDious.
# Copyright © 2024 iN_siDious. All rights reserved.
import sys,os
import random
from math import inf,ceil,sqrt
from string import ascii_lowercase,ascii_uppercase
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import heappushpop, heapify, heappop, heappush
from bisect import bisect_left,bisect_right
from types import GeneratorType
from random import randint
RANDOM = randint(1, 10 ** 10)
class op(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(op, self).__hash__() ^ RANDOM
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
input = lambda: sys.stdin.buffer.readline().decode().strip()
out=sys.stdout.write
def S():
    return input()
def I():
    return int(input())
def MI():
    return map(int, input().split())
def MF():
    return map(float, input().split())
def MS():
    return input().split()
def LS():
    return list(input().split())
def LI():
    return list(map(int,input().split()))
def print1(x):
    return out(str(x)+"\n")
def print2(x,y):
    return out(str(x)+" "+str(y)+"\n")
def print3(x,y,z):
    return out(str(x)+" "+str(y)+" "+str(z)+"\n")
def Query(i,j):
    print3('?', i, j)
    sys.stdout.flush()
    qi=I()
    return qi
def print_arr(arr):
    out(' '.join(map(str,arr)))
    out(str("\n"))

# ----------------------------- # ----------------------------- #
@bootstrap
def tarjan(x):
    global cnt # 当前时间戳
    cnt += 1
    dfn[x] = low[x] = cnt
    flag = 0  # 子树中不满足条件的点的数量
    for y in g[x]:
        if not dfn[y]:
            yield tarjan(y)
            low[x] = min(low[x], low[y]) # 树边更新low值
            if low[y] >= dfn[x]: # 返祖边在x下侧，只要有x就是割点
                flag += 1
                if (x != root or flag > 1): boo[x] = 1 # 如果是root，还要保证儿子数大于1
        else: low[x] = min(low[x], dfn[y]) # 非树边更新 low值
    yield None

n,m = MI()
g = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = MI()
    if x == y: continue
    g[x].append(y)
    g[y].append(x)

cnt = 0  # 用于记录当前时间戳
dfn, boo = [0]*(n+1), [0]*(n+1) # dfn:时间戳, boo:是否为割点
low = [i for i in range(n+1)]
for i in range(1,n+1):
    if not dfn[i]:
        root = i
        tarjan(i)
ans = []
for i in range(1,n+1):
    if boo[i]: ans.append(i)
print1(len(ans))
print_arr(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
def add(x,y,z):
    global tot
    tot += 1
    ver[tot],edge[tot] = y,z
    nxt[tot],head[x] = head[x],tot
    
def tarjan(x, in_edge):
    global cnt  # 在solve里面用 nonlocal cnt
    cnt += 1
    dfn[x] = low[x] = cnt
    i = head[x]
    while i:
        y = ver[i]
        if not dfn[y]:
            tarjan(y,i)
            low[x] = min(low[x], low[y])
            if low[y] > dfn[x]: # (x,y) 为桥
                bridge[i] = bridge[i^1] = 1
        elif i != (in_edge^1): # 忽略反向边
            low[x] = min(low[x],dfn[y])
        i = nxt[i]
    
n,m = map(int, input().split())
head = [0]*(n+1)
ver,edge,nxt = [0]*(2*m+2),[0]*(2*m+2),[0]*(2*m+2)
tot = 1

for i in range(m):
    x,y,z = map(int, input().split())
    add(x,y,z)
    add(y,x,z)

bridge = [0]*(2*m+1)
dfn,low = [0]*(n+1), [i for i in range(n+1)]
cnt = 0
for i in range(1,n+1):
    if not dfn[i]:tarjan(i,0)
for i in range(2,tot+1,2):
    if bridge[i]: print(ver[i^1],ver[i])

4、边双连通分量()

​ 把割边删了之后，每一个连通块都是一个边双连通分量，可以用 数组记录结点属于的便双连通分量的编号。

缩点

​ 把每个 看成一个结点，把桥 看成连接 和 的无向边，会产生一棵树(若原来的无向图不连通，则产生森林)，python代码如下。

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
import sys
input = sys.stdin.readline

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

def tarjan(x, in_edge):
    global cnt  # 在solve里面用 nonlocal cnt
    cnt += 1
    dfn[x] = low[x] = cnt
    i = head[x]
    while i:
        y = ver[i]
        if not dfn[y]: # 是树边
            tarjan(y,i)
            low[x] = min(low[x], low[y])
            if low[y] > dfn[x]: # (x,y) 为桥
                bridge[i] = bridge[i^1] = 1
        elif i != (in_edge^1): # 忽略反向边
            low[x] = min(low[x], dfn[y])
        i = nxt[i]

def dfs(x):  
    """类似找连通块的方法对 e-DCC 染色"""
    c[x] = dcc
    i = head[x]
    while i:
        y = ver[i]
        if c[y] or bridge[i]: continue
        dfs(y)
        i = nxt[i]

n,m = map(int, input().split())
head = [0]*(n+1)
ver,nxt,edge = [0]*(2*m+2),[0]*(2*m+2),[0]*(2*m+2)
tot = 1
for i in range(m):
    x,y,z = map(int, input().split())
    add(x,y,z)
    add(y,x,z)

bridge = [0]*(m*2+2)
dfn,low = [0]*(n+1),[i for i in range(n+1)]
cnt = 0
for i in range(1,n+1):
    if not dfn[i]: tarjan(i, 0)

c,dcc = [0]*(n+1), 0
for i in range(1,n+1):
    if not c[i]:
        dcc += 1
        dfs(i)

5、点双连通分量()

求

​ 这里需要注意的是割点可能属于多个点双连通分量，为了求出点双连通分量，需要在 算法的过程中维护一个栈，并按照如下方法维护栈中元素。

  1. 当一个结点第一次被访问时，把该结点入栈。
  2. 当割点判定法则中的条件 成立时，无论 是否为根，都要：
    • 1）从栈顶不断弹出结点，直至结点 被弹出。
    • 2）刚才弹出的所有结点与结点 共同构成一个 。

缩点

的缩点比 的缩点复杂——因为一个割点可能属于多个 。设图有 个割点和 个 。我们建立一张包含 个结点的新图，把每个 和每个割点都作为新图中的结点，并在每个割点和包含它的所有 之间连边。这张新图其实是一张树或森林。

python代码如下：

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
# Created by iN_siDious.
# Copyright © 2024 iN_siDious. All rights reserved.
import sys,os
import random
from math import inf,ceil,sqrt
from string import ascii_lowercase,ascii_uppercase
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import heappushpop, heapify, heappop, heappush
from bisect import bisect_left,bisect_right
from types import GeneratorType
from random import randint
RANDOM = randint(1, 10 ** 10)
class op(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(op, self).__hash__() ^ RANDOM
# --------------------
# 手写栈模板
# 克服py栈太浅的问题
# 注意要用yield 不要用return
# 函数结尾要写yield None
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
input = lambda: sys.stdin.buffer.readline().decode().strip()
out=sys.stdout.write
def S():
    return input()
def I():
    return int(input())
def MI():
    return map(int, input().split())
def MF():
    return map(float, input().split())
def MS():
    return input().split()
def LS():
    return list(input().split())
def LI():
    return list(map(int,input().split()))
def print1(x):
    return out(str(x)+"\n")
def print2(x,y):
    return out(str(x)+" "+str(y)+"\n")
def print3(x,y,z):
    return out(str(x)+" "+str(y)+" "+str(z)+"\n")
def Query(i,j):
    print3('?', i, j)
    sys.stdout.flush()
    qi=I()
    return qi
def print_arr(arr):
    out(' '.join(map(str,arr)))
    out(str("\n"))

# ----------------------------- # ----------------------------- #
@bootstrap
def tarjan(x):
    global cnt,tot # 当前时间戳
    cnt += 1
    dfn[x] = low[x] = cnt
    st.append(x)
    if x == root and len(g[x]) == 0:
        tot += 1
        dcc[tot].append(x)
        yield None
    flag = 0  # 子树中不满足条件的点的数量
    for y in g[x]:
        if not dfn[y]:
            yield tarjan(y)
            low[x] = min(low[x], low[y]) # 树边更新low值
            if low[y] >= dfn[x]: # 返祖边在x下侧，只要有x就是割点
                flag,tot= flag + 1, tot + 1
                if (x != root or flag > 1): boo[x] = 1 # 如果是root，还要保证儿子数大于1
                while st[-1] != x:
                    dcc[tot].append(st.pop())
                dcc[tot].append(x)
        else: low[x] = min(low[x], dfn[y]) # 非树边更新 low值
    yield None

n,m = MI()
g = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = MI()
    if x == y: continue
    g[x].append(y)
    g[y].append(x)

"""求v-DCC"""
cnt,tot = 0,0  # 用于记录当前时间戳, dcc编号
dfn, boo = [0]*(n+1), [0]*(n+1) # dfn:时间戳, boo:是否为割点
low = [i for i in range(n+1)]
st,dcc = [],[[] for i in range(n+1)]  # stack, v-DCC
for i in range(1,n+1):
    if not dfn[i]:
        root = i
        tarjan(i)

"""v-DCC 缩点"""
cnt = tot
new_id = [0]*(n+1)
for i in range(1,n+1):
    if boo[i]:  # 给每个割点一个新的编号(从 cnt+1 开始)
        cnt += 1
        new_id[i] = cnt
gg = [[] for _ in range(cnt + 1)]
c = [0]*(n+1) # v-DCC 染色
for i in range(1,tot+1):
    for j in range(len(dcc[i])):
        x = dcc[i][j]
        if boo[x]:
            gg[i].append(new_id[x])
            gg[new_id[x]].append(i)
        else: c[x] = i  # 除割点外，其他点仅属于1个 v-DCC

6、有向图的连通性

一些概念

​ 给定有向图，若存在 ，满足从 出发能够到达 中所有的点则称 是一个“流图”，记为 ，其中 为流图的源点。流图中每条有向边 必然是以下四种之一：1、树边 2、前向边 3、返祖边(后向边) 4、横插边。

​ 有向图的极大强连通子图称为“强连通分量”。

1、 算法

​ 对原图进行一次 ，分成若干棵树，再以第一次搜索的出栈顺序对原图的返图进行 ，和 能到的是在同一个连通分量中。

2、 算法与有向图的强连通分量

强连通分量 以及 缩点

​ 在这里 算法的的基本思路是对于每一个点，尽量找到能与他构成环的所有结点。为了找到通过“后向边”和“横插边”构成的环， 算法在 的同时维护一个栈，当访问到结点 时，栈中需要保存以下两类结点：

  1. 搜索树上 的祖先结点，记为集合 。设 。若存在后向边 ，则 与 到 的路径一定形成环。
  2. 已经访问过并且存在一条路径到达 的结点。设 是这样一个点，从 出发存在一条路径到达 。若存在横插边 ，则 、到的路径、到的路径 形成一个环。

综上所述，栈中结点就是能与从 出发的“后向边”和“横插边”形成环的结点。

​ 设 表示流图的搜索树中以 为根的子树。 定义为从 出发的有向边能连接到的还在栈中 值最小的点。根据定义， 算法计算“追溯值” 的步骤如下：

  1. 当结点 第一次被访问时，把 入栈，初始化 。
  2. 扫描 的每条出边 :
    • 若 没被访问过，则说明 是树边，递归访问 ，从 回溯后，令 。
    • 若 被访问过，并且 在栈中，则令 。
  3. 从 回溯之前，判断是否有 。若成立，则不断从栈中弹出结点，直至 出栈。意味着就是这个强连通分量中在搜索树上最高的点

python code:

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
input = sys.stdin.readline

def tarjan(x):
    global cnt,tot # 当前时间戳
    cnt += 1
    dfn[x] = low[x] = cnt
    st.append(x)
    ins[x] = 1
    for y in g[x]:
        if not dfn[y]:
            tarjan(y)
            low[x] = min(low[x], low[y])
        elif ins[y]:
            low[x] = min(low[x],dfn[y])
    if dfn[x] == low[x]:
        tot += 1
        while st[-1] != x:
            y = st.pop()
            ins[y] = 0
            c[y] = tot, scc[tot].append(y)
        y = st.pop()
        ins[y] = 0
        c[y] = tot, scc[tot].append(y)
        
cnt,tot = 0,0  # 用于记录当前时间戳, scc编号
n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int, input().split())
    if x == y: continue
    g[x].append(y)
    g[y].append(x)

"""求SCC"""
dfn,c = [0]*(n+1),[0]*(n+1) # dfn:时间戳, c:SCC编号
low = [i for i in range(n+1)]
scc = [[] for _ in range(n+1)]
st,ins = [],[0]*(n+1) # stack, if in stack or not
for i in range(1,n+1):
    if not dfn[i]: tarjan(i)

"""SCC缩点"""
gc = [[] for _ in range(tot+1)]
for x in range(1,n+1):
    for y in g[x]:
        if c[x] == c[y]: continue
        g[c[x]].append(c[y])

图匹配相关python模板

1、二分图的判定算法模板

二分图的判定及性质：

1) 静态二分图的判定： dfs染色
2) 动态二分图的判定： 扩展域并查集 / 带边权的并查集
3) 性质1：至少有2个顶点且没有奇环
4) 性质2：最小路径覆盖 = 顶点数 - 最大匹配

konig定理：

二分图的最大匹配数等于最小点覆盖数

2、匈牙利算法模板

匈牙利算法（增广路算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
邻接矩阵存图时间复杂度为O(n^3)
邻接表存图时间复杂度为O(nm)
"""
#邻接表存图
def dfs(x):
    for y,w in g[x]:
        if vis[y]: continue  # 在dfs时注意两边集合的含义，如有特殊含义则需要增加判断条件
        vis[y] = True
        if not link[y] or dfs(link[y]):
            link[y] = x
            return True
    return False

ans = 0
link = [0]*(n+1)
for i in range(1,n+1):
    vis = [False]*(n+1)
    if dfs(i): ans += 1

3、KM算法模板

• 算法思路：

​ 最开始将每个左边节点连的权值最大的边视为有效边，在匹配给过程当中如果某个点找不到匹配点，则选择将一些无效边改成有效边继续去匹配，选择的这些无效边其实是换掉的原来的某条有效边，那么我们肯定选换掉的代价最小的。

• 具体操作：

1、给每个点预设一个顶标，只有两个端点的顶标加起来等于边权的边，我们才认为是有效边，即的时候才是有效边

2、最开始左集合的每个点的顶标为他连出去权值最大的边的权值，右集合每个点顶标为0，当匹配失败的时候，我们枚举之前的左集合本次尝试匹配遍历过的点，在他们的连向右集合未遍历的点的边中找一个与顶标和差值最小的边（即在当前的无效边中找一个差值最小的边），即 最小的边（可理解为找出一条损失最小的找出一条增广路。）找到之后修改顶标：左侧所有枚举过的点减去delta，右边所有遍历过的点加上delta，这样原来的有效边还是有效边，而我们新加的边也已经加上了。

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
import sys

inf, _inf = float("inf"), float('-inf')
def km():
    def dfs(x):
        visx[x] = 1
        for i in range(1,H+1):
            if not visy[i] and lx[x] + ly[i] == g[x][i]:  #两顶标相加等于边权为有效边
                visy[i] = 1
                if link[i] == 0 or dfs(link[i]):
                    link[i] = x
                    return 1
        return 0
    
    for i in range(1,P+1):
        while 1:
            visx,visy = [0]*(P+1), [0]*(H+1)
            if dfs(i): break
            d = inf
            for j in range(1,P+1):
                if visx[j]:  # 枚举所有左集合访问过的点，找到差值最小的 d
                    for k in range(1,H+1):
                        if not visy[k]: d = min(d, lx[j] + ly[k] - g[j][k])
            if d == inf: return 0
            for j in range(1,P+1):
                if visx[j]: lx[j] -= d
            for j in range(1,H+1):
                if visy[j]: ly[j] += d
    return 1

"""P为人的数量，H为房子的数量，人和房子分别为左右集合"""
lx,ly,link = [_inf]*(P+1),[0]*(H+1),[0]*(P+1)
for i in range(1,P+1):  #初始化顶标
    for j in range(1,H+1):
        if g[i][j] != 0:
            lx[i] = max(lx[i], g[i][j])
if km() == 1:
    ans = 0
    for i in range(1,H+1):
        ans += g[link[i]][i] # link记录了每个房子（右集合）匹配到的人的下标（左集合）
    print(-ans)   # 题目求的是最小匹配，我们将边取负，求最大匹配，输出相反数

4、稳定婚姻类问题思路

可以通俗的理解为有n个男生，n个女生，每个人都每个异性都有 一个好感度，要求两两配对结为夫妻，使不存在夫妻uv和ab，满足u对b的好感度大于u对v的好感度，b对u的好感度大于b对a的 好感度。求这种稳定婚姻的方案。

Gale-Shapley算法

• 首先，男生需要按照希望与之交往的顺序给所有女生排序，即最理想 的女友排在最前、最不理想的放在最后。同样，每个女生也需要给男 生排序。接着，男生将按照自己的名单一轮一轮地去追求喜欢的女生， 女生也将按照自己的名单接受或拒绝对方的追求。

• 第一轮，每个男生都向自己名单上排在首位的女生表白。此时，一个 女生可能面对的情况有三种：没有人跟她表白、只有一人跟她表白、 有不止一人跟她表白。在第一种情况下，这个女生什么都不做，继续 等待即可；在第二种情况下，女生接受那个人的表白，答应暂时和他 做男女朋友；在第三种情况下，女生从所有追求者中选择自己最喜欢 的那一位，答应和他暂时做男女朋友，并拒绝其他所有的追求者。

• 第一轮结束后，有些男生已经有女朋友了而有些男生仍然是单身狗。在第二轮表白 行动中，每个单身男都会从所有还没拒绝过自己的女生中选出自己最喜欢的那一个， 并向她表白，不管她现在是否是单身。和第一轮一样，每个被表白的女生需要从表 白者中选择最喜欢的男生，并拒绝其他追求者。注意，如果这个女生当前已经有男 朋友了，当她遇到了更好的追求者时，她将毫不犹豫地和现男友分手，投向新追求 者的怀抱。这样以来，一些单身狗将脱单，而一些倒霉的恩爱狗（男）也会被分手， 重新进入单身狗的行列。

• 在以后的每一轮中，单身狗们将发扬愈挫愈勇的顽强精神，继续追求列表中的下 一个女生；女生则从包括现男友在内的所有追求者中选择最好的一个，并给其他所 有追求者发好人卡。这样一轮一轮地进行下去，直到某个时刻所有人都不再单身， 那么下一轮将不会有任何新的表白，每个人的对象也都将固定下来，整个过程自动 结束——此时的搭配就一定是稳定的了。

5、一般图匹配算法模板(带花树问题)

待更新

网络流算法python模板

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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
# Created by iN_siDious.
# Copyright © 2024 iN_siDious. All rights reserved.
import sys,os
import random
from math import inf,ceil,sqrt
from string import ascii_lowercase,ascii_uppercase
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import heappushpop, heapify, heappop, heappush
from bisect import bisect_left,bisect_right
from types import GeneratorType
from random import randint
RANDOM = randint(1, 10 ** 10)
class op(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(op, self).__hash__() ^ RANDOM
# --------------------
# 手写栈模板
# 克服py栈太浅的问题
# 注意要用yield 不要用return
# 函数结尾要写yield None
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType: # 如果下一级还是生成器，就继续递归
                    stack.append(to)
                    to = next(to)
                else: # 如果下一级已经开始返回值了，说明需要回到上一级了
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

input = lambda: sys.stdin.buffer.readline().decode().strip()
out=sys.stdout.write
def S():
    return input()
def I():
    return int(input())
def MI():
    return map(int, input().split())
def MF():
    return map(float, input().split())
def MS():
    return input().split()
def LS():
    return list(input().split())
def LI():
    return list(map(int,input().split()))
def print1(x):
    return out(str(x)+"\n")
def print2(x,y):
    return out(str(x)+" "+str(y)+"\n")
def print3(x,y,z):
    return out(str(x)+" "+str(y)+" "+str(z)+"\n")
def Query(i,j):
    print3('?', i, j)
    sys.stdout.flush()
    qi=I()
    return qi
def print_arr(arr):
    out(' '.join(map(str,arr)))
    out(str("\n"))

# ----------------------------- # ----------------------------- #

# dinic算法求最大流
# 用法示例
# 创建一个 Maxflow 实例
# mf = Maxflow(100)  # n 是节点数
# 添加边，例如：
# mf.add_edge(u, v, cap)
# 计算最大流
# max_flow = mf.max_flow(source, sink)
class Maxflow:
    # n 节点数， 从0开始编号
    def __init__(self, n):
        self.n = n
        self.G = [[] for _ in range(n)]
        self.depth = [0] * n
        # cur[u] 表示当前弧下标
        self.cur = [0] * n

    # 添加一条从 u 到 v 的容量为 cap 的边
    def add_edge(self, u, v, cap):
        # 正向边 u -> v
        self.G[u].append([v, cap, len(self.G[v])])  # 分别存(该边的终点，容量，反向边的idx)
        # 反向边 v -> u，初始容量为 0
        self.G[v].append([u, 0, len(self.G[u]) - 1])  # 分别存(该边的终点，容量，正向边的idx)

    # 从源点出发进行一次bfs，计算出每个点的深度
    # 对当前残差图的BFS构造一个level 图（或为顶点分配深度）, 并检查是否更多的流量是可能的。
    def bfs(self, s, t):
        self.depth = [-1] * self.n
        self.depth[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, _ in self.G[u]:
                if self.depth[v] == -1 and cap > 0:
                    self.depth[v] = self.depth[u] + 1
                    q.append(v)
        return self.depth[t] != -1

    # 从 u 出发，沿着深度优先搜索的路径，不断增广
    def dfs(self, u, t, f=inf):
        if u == t:
            return f
        max_flow = 0
        while self.cur[u] < len(self.G[u]):
            v, cap, rev = self.G[u][self.cur[u]]
            # 只有当 u 的深度加 1 之后等于 v 的深度时，我们才让他流 [不能走回头路]
            if cap > 0 and self.depth[v] == self.depth[u] + 1:
                # 流多少呢，能装多少流就流多少
                df = self.dfs(v, t, min(f - max_flow, cap))
                if df > 0:
                    self.G[u][self.cur[u]][1] -= df
                    self.G[v][rev][1] += df
                    max_flow += df
                    if max_flow == f:
                        break
            # 只有当前面的边都已经流满/不可达，我们才更新 cur[u]，下一次直接从第cur[u]条边开始枚举
            self.cur[u] += 1
        return max_flow

    # s 是源点，t 是汇点
    def max_flow(self, s, t):
        total_flow = 0
        # 当找不到增广路时，bfs 返回 false
        while self.bfs(s, t):
            self.cur = [0] * self.n
            flow = self.dfs(s, t)
            while flow > 0:
                total_flow += flow
                flow = self.dfs(s, t)
        return total_flow

    # 用手写栈优化dfs
    @bootstrap
    def dfs_bootstrap(self, u, t, f=inf):
        if u == t:
            yield f
        max_flow = 0
        while self.cur[u] < len(self.G[u]):
            v, cap, rev = self.G[u][self.cur[u]]
            # 只有当 u 的深度加 1 之后等于 v 的深度时，我们才让他流 [不能走回头路]
            if cap > 0 and self.depth[v] == self.depth[u] + 1:
                # 流多少呢，能装多少流就流多少
                df = yield self.dfs_bootstrap(v, t, min(f - max_flow, cap))
                if df > 0:
                    self.G[u][self.cur[u]][1] -= df
                    self.G[v][rev][1] += df
                    max_flow += df
                    if max_flow == f:
                        break
            # 只有当前面的边都已经流满/不可达，我们才更新 cur[u]，下一次直接从第cur[u]条边开始枚举
            self.cur[u] += 1
        yield max_flow

    def max_flow_bootstrap(self, s, t):
        total_flow = 0
        # 当找不到增广路时，bfs 返回 false
        while self.bfs(s, t):
            self.cur = [0] * self.n
            flow = self.dfs_bootstrap(s, t)
            while flow > 0:
                total_flow += flow
                flow = self.dfs_bootstrap(s, t)
        return total_flow


n,m,s,t = MI()
mf = Maxflow(n+1)

for _ in range(m):
    x,y,z = MI()
    mf.add_edge(x,y,z)

print1(mf.max_flow_bootstrap(s,t))

ISAP算法

待更新

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模板 介绍 图匹配 图论 技术部寒假算法培训 最小生成树 牛客竞赛 蓝书 题目汇总