数据结构（五）：图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# dijkstra
def dij(g,s):
	pq,d = [(0,s)], [inf]*n
	d[s] = 0
	while pq:
		w,u = heappop(pq)
		if w>d[u]:
			continue
		for v,w2 in g[u]:
			nw = w+w2
			if nw<d[v]:
				d[v] = nw
				heappush(pq, (nw,v))
	return d

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# dijkstra
def dij(g,s):
	Q, d = set(range(n)), [inf]*n
	d[s] = 0
	while Q:
		u = min(Q, key=d.__getitem__)
		Q.remove(u)
		for v, w in g[u]:
			if v in Q:
				d[v] = min(d[v], d[u]+w)

1
2
3
4
5

# floyd
for i in range(n):
    f[i][i] = 0
for k,i,j in product(range(n),range(n),range(n)):
	f[i][j] = min(f[i][j],f[i][k]+f[k][j])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Bellman-Ford 
def BF(edges,s):
	d = [inf]*n
	d[s] = 0
	for _ in range(n-1):
		flag = True
		for u,v,w in edges:
			if d[u]+w<d[v]:
				d[v] = d[u]+w
				flag = False
		if flag:
			break
	return d

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# spfa
def spfa(g,s):
    d = [inf] * n
    d[s] = 0
    Q, vis = deque([s]), {s}
    while Q:
        u = Q.popleft()
        vis.remove(u)
        for v, w in g[u]:
            if d[u]+w<d[v]:
                d[v] = d[u]+w
                if v not in vis:
                    vis.add(v)
                    Q.append(v)
    return d

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

n = len(g)
C = []
vis = [0]*n
rg = [[] for _ in range(n)]
for u in range(n):
	A = []
	while not vis[u]:
		A.append(u)
		vis[u] = 1
		u = g[u]
	if u in A:
		i = A.index(u)
		C.append(A[i:])
		A = A[:i]
	for a,b in pairwise(A+[u]):
		rg[b].append(a)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# 割点
def tarjan(u,root):
	nonlocal t
	dfn[u]=low[u]=t=t+1
	s = 0
	for v in g[u]:
		if not dfn[v]:
			tarjan(v,0)
			low[u] = min(low[u],low[v])
			s += low[v]>=dfn[u]
		else:
			low[u] = min(low[u],dfn[v])
	cut[u] = s>root
dfn,low,t = [0]*n,[0]*n,0
cut = [0]*n
tarjan(0,1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# 桥
def tarjan(u,fa):
	nonlocal t
	dfn[u]=low[u]=t=t+1
	for v in g[u]:
		if not dfn[v]:
			tarjan(v,u)
			low[u] = min(low[u],low[v])
			if low[v]>dfn[u]:
				bridge.append([u,v])
		elif v!=fa:
			low[u] = min(low[u],dfn[v])
dfn,low,t = [0]*n,[0]*n,0
bridge = []
tarjan(0,-1)

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

# 强连通分量、边双连通分量
def tarjan(u,fa):
	nonlocal t,i
	dfn[u]=low[u]=t=t+1
	sk.append(u)
	vis[u] = 1
	for v in g[u]:
		if not dfn[v]:
			tarjan(v,u)
			low[u] = min(low[u],low[v])
		elif v!=fa and vis[v]:
			low[u] = min(low[u],dfn[v])
	if low[u]==dfn[u]:
		i += 1
		v = -1
		while v!=u:
			v = sk.pop()
			vis[v] = 0
			scc[v] = i
dfn,low,vis,sk = [0]*n,[0]*n,[0]*n,[]
t,i = 0,0
scc = []
tarjan(0,-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

# 点双连通分量
def tarjan(u,root):
	if root and not g[u]:
		dcc.append([u])
	nonlocal t
	dfn[u]=low[u]=t=t+1
	sk.append(u)
	s = 0
	for v in g[u]:
		if not dfn[v]:
			tarjan(v,0)
			low[u] = min(low[u],low[v])
			if low[v]>=dfn[u]:
				s += 1
				dcc.append([])
				while sk[-1]!=v:
					dcc[-1].append(sk.pop())
				dcc[-1].extend([sk.pop(),u])
		else:
			low[u] = min(low[u],dfn[v])
	cut[u] = s>root
dfn,low,sk,t = [0]*n,[0]*n,[],0
dcc,cut = [],[0]*n
tarjan(0,1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# 二分图最大匹配，匈牙利
def hgr(g):            # g 是二分图中每个 x 对应的 y 列表
    def find(x):
        for y in g[x]:
            if y not in vis:
                vis.add(y)
                if y not in d or find(d[y]):
                    d[y]=x
                    return True
        return False
    res,vis,d = 0,set(),{}
    for x in g:
        res += find(x)
        vis.clear()
    return res

 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

# 二分图最大权完美匹配，匈牙利
def km(g):                   # g 是 n-n 完全二分图的权值
    def bfs(i): 
        slack = [inf]*n
        vis = [0]*(n+1)
        pre = [-1]*n
        j=nj=-1
        d[j] = i
        while d[j]!=-1:
            delta = inf
            x = d[j]
            vis[j]=True
            for y in range(n):
                if vis[y]:
                    continue
                tmp=lx[x]+ly[y]-g[x][y]
                if slack[y]>tmp:
                    slack[y]=tmp
                    pre[y]=j
                if slack[y]<delta:
                    delta=slack[y]
                    nj = y
            lx[i]-=delta
            for y in range(n):
                if vis[y]:
                    lx[d[y]]-=delta
                    ly[y]+=delta
                else:
                    slack[y]-=delta
            j = nj
        while j!=-1:
            d[j]=d[pre[j]]
            j=pre[j]

    n = len(g)
    d = [-1]*(n+1)
    lx = [max(row) for row in g]
    ly = [0]*n
    for i in range(n):
        bfs(i)
    return sum(g[d[y]][y] for y in range(n))

 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

# 最大流
class Dinic:
    def __init__(self,):
        self.g = defaultdict(list)          # g 是图中每个 u 对应的 v 列表
        self.h = {}                         # h 是图中每个 u 离源点 s 的距离
        self.p = defaultdict(int)           # p 是当前弧优化，跳过已增广的边

    def add(self,u,v,c):                    # 顶点 u 和 v 连边，容量 c
        self.g[u].append([v,len(self.g[v]),c])
        self.g[v].append([u,len(self.g[u])-1,0])

    def bfs(self,s,t):
        self.h = {s:0}
        self.p = defaultdict(int)
        Q = deque([s])
        while Q:
            u = Q.popleft()
            for v,_,c in self.g[u]:
                if v not in self.h and c>0:
                    Q.append(v)
                    self.h[v]=self.h[u]+1
        return t in self.h

    def dfs(self,u,t,flow):
        if u==t:
            return flow
        res = 0
        for i in range(self.p[u],len(self.g[u])):
            v,j,c = self.g[u][i]
            if self.h[v]==self.h[u]+1 and c>0:
                a = self.dfs(v,t,min(flow,c))
                flow -= a
                self.g[u][i][-1]-=a
                self.g[v][j][-1]+=a
                res += a
            self.p[u] += 1
        return res

    def cal(self,s,t):
        res = 0
        while self.bfs(s,t):
            res += self.dfs(s,t,inf)
        return res         self.g[u][i][-1]-=a
                self.g[v][j][-1]+=a
                res += a
            self.p[u] += 1
        return res

    def cal(self,s,t):
        res = 0
        while self.bfs(s,t):
            res += self.dfs(s,t,inf)
        return res

 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

# 最小费用最大流
class Dinic:
    def __init__(self,):
        self.g = defaultdict(list)          # g 是图中每个 u 对应的 v 列表
        self.h = defaultdict(lambda:inf)    # h 是图中每个 u 离源点 s 的距离
        self.p = defaultdict(int)           # p 是当前弧优化，跳过已增广的边
        self.vis = set()

    def add(self,u,v,c,w):                  # 顶点 u 和 v 连边，容量 c，费用 w
        self.g[u].append([v,len(self.g[v]),c,w])
        self.g[v].append([u,len(self.g[u])-1,0,-w])

    def spfa(self,s,t):
        self.h.clear()
        self.h[s]=0
        Q, vis = deque([s]), {s}
        while Q:
            u = Q.popleft()
            vis.remove(u)
            for v,_,c,w in self.g[u]:
                if c>0 and self.h[u]+w<self.h[v]:
                    self.h[v] = self.h[u]+w
                    if v not in vis:
                        vis.add(v)
                        Q.append(v)
        return self.h[t]<inf

    def dfs(self,u,t,flow):
        if u==t:
            return flow
        self.vis.add(u)
        res = 0
        for i in range(self.p[u],len(self.g[u])):
            v,j,c,w = self.g[u][i]
            if c>0 and v not in self.vis and self.h[v]==self.h[u]+w:
                a = self.dfs(v,t,min(flow,c))
                flow -= a
                self.g[u][i][2]-=a
                self.g[v][j][2]+=a
                res += a
            self.p[u] += 1
        self.vis.remove(u)
        return res

    def cal(self,s,t):
        res = 0
        while self.spfa(s,t):
            res += self.dfs(s,t,inf)*self.h[t]
            self.p.clear()
        return res