头像

皓首不倦


访客:17107

在线 


活动打卡代码 AcWing 961. 最大获利

皓首不倦
1小时前


'''
转换成最大闭合子图问题解决,
用户群为正权值点,中转站为负权值点,正权值点依赖于一些负权值点,负权值点没有对外依赖,
因此每一个选择方案都对应于原图的一个闭合子图,用最大流求闭合点集的最大权值和即可
'''

from typing import List
from collections import deque
import sys

class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow


n, m = map(int, input().split())
S, T = n+m + 1, n+m + 2
cost = list(map(int, input().split()))


edges = []
for i, p in enumerate(cost):
    edges.append((i+1, T, p))

ans = 0
for i in range(n+1, n+m+1):
    a, b, c = map(int, input().split())
    edges.append((i, a, 0x7fffffff))
    edges.append((i, b, 0x7fffffff))
    edges.append((S, i, c))
    ans += c

ans -= FortdFulkerson(edges, S, T, n+m+2, len(edges)).getMaxFlow()
print(ans)




皓首不倦
1小时前


'''
转换成最大闭合子图问题解决,
用户群为正权值点,中转站为负权值点,正权值点依赖于一些负权值点,负权值点没有对外依赖,
因此每一个选择方案都对应于原图的一个闭合子图,用最大流求闭合点集的最大权值和即可
'''

from typing import List
from collections import deque
import sys

class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow


n, m = map(int, input().split())
S, T = n+m + 1, n+m + 2
cost = list(map(int, input().split()))


edges = []
for i, p in enumerate(cost):
    edges.append((i+1, T, p))

ans = 0
for i in range(n+1, n+m+1):
    a, b, c = map(int, input().split())
    edges.append((i, a, 0x7fffffff))
    edges.append((i, b, 0x7fffffff))
    edges.append((S, i, c))
    ans += c

ans -= FortdFulkerson(edges, S, T, n+m+2, len(edges)).getMaxFlow()
print(ans)



活动打卡代码 AcWing 2280. 最优标号

皓首不倦
16小时前
from typing import List
from collections import deque

import sys
class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow



n, m = map(int, input().split())
e = []

for i in range(m):
    a, b = map(int, input().split())
    e.append((a, b, 1))
    e.append((b, a, 1))

k = int(input())
label = {}
for i in range(k):
    a, b = map(int, input().split())
    label[a] = b

S, T = n+1, n+2
ans = 0
for bit in range(32):

    ee = []
    for node, val in label.items():
        if val & (1 << bit):
           ee.append((node, T, 0x7fffffff))
           ee.append((T, node, 0x7fffffff))
        else:
            ee.append((node, S, 0x7fffffff))
            ee.append((S, node, 0x7fffffff))

    edges = e + ee
    max_flow = FortdFulkerson(edges, S, T, n+2, len(edges)).getMaxFlow()
    ans += (1 << bit) * max_flow

print(ans)



皓首不倦
16小时前

acwing2280.png


from typing import List
from collections import deque

import sys
class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow



n, m = map(int, input().split())
e = []

for i in range(m):
    a, b = map(int, input().split())
    e.append((a, b, 1))
    e.append((b, a, 1))

k = int(input())
label = {}
for i in range(k):
    a, b = map(int, input().split())
    label[a] = b

S, T = n+1, n+2
ans = 0
for bit in range(32):

    ee = []
    for node, val in label.items():
        if val & (1 << bit):
           ee.append((node, T, 0x7fffffff))
           ee.append((T, node, 0x7fffffff))
        else:
            ee.append((node, S, 0x7fffffff))
            ee.append((S, node, 0x7fffffff))

    edges = e + ee
    max_flow = FortdFulkerson(edges, S, T, n+2, len(edges)).getMaxFlow()
    ans += (1 << bit) * max_flow

print(ans)




活动打卡代码 AcWing 2279. 网络战争

皓首不倦
18小时前
EPSILON = 1e-7
from typing import List
from collections import deque

import sys
class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow


n, m, S, T = map(int, input().split())
e = []
max_w = -0x7fffffff
for _ in range(m):
    a, b, w = map(int, input().split())
    e.append((a, b, w))
    max_w = max(w, max_w)

l, r = 0, max_w
ans = None
while abs(l - r) > EPSILON:
    mid = l + (r - l) / 2

    total = 0
    edges = []
    for a, b, w in e:
        if w <= mid:
            total -= mid - w
        else:
            edges.append((a, b, w-mid))
            edges.append((b, a, w-mid))

    max_flow = FortdFulkerson(edges, S, T, n, len(edges)).getMaxFlow()
    if max_flow + total < 0:
        ans = r
        r = mid
    else:
        l = mid

print('{:.2f}'.format(ans))




皓首不倦
18小时前

acwing2279.png



EPSILON = 1e-7
from typing import List
from collections import deque

import sys
class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow


n, m, S, T = map(int, input().split())
e = []
max_w = -0x7fffffff
for _ in range(m):
    a, b, w = map(int, input().split())
    e.append((a, b, w))
    max_w = max(w, max_w)

l, r = 0, max_w
ans = None
while abs(l - r) > EPSILON:
    mid = l + (r - l) / 2

    total = 0
    edges = []
    for a, b, w in e:
        if w <= mid:
            total -= mid - w
        else:
            edges.append((a, b, w-mid))
            edges.append((b, a, w-mid))

    max_flow = FortdFulkerson(edges, S, T, n, len(edges)).getMaxFlow()
    if max_flow + total < 0:
        ans = r
        r = mid
    else:
        l = mid

print('{:.2f}'.format(ans))







皓首不倦
20小时前

'''
求最小割和求最大流是等价的,直接用Dinic求最大流即可
'''

from typing import List
from collections import deque

class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    #返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num*2 + 1)            # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num*2 + 1)            # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num*2 + 1)           # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)              # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)            # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)            # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度
        orig_flow = [0] * (self.max_edge_num + 1)       # 原图中有向边的流量

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False


        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]     # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node]+1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx^1], flow = f[idx]-t, f[idx^1]+t, flow+t

                    # 更新原图边的流量
                    if self.edges[idx>>1][0] == node:
                        orig_flow[idx>>1] += t
                    else:
                        orig_flow[idx>>1] -= t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow, [(self.edges[i][0], self.edges[i][1], orig_flow[i], self.edges[i][2]) for i in range(len(self.edges))]

n, m, start, end = map(int, input().split())
link = {}
for _ in range(m):
    a, b, w = map(int, input().split())

    if (a, b) not in link:
        link[(a, b)] = w
    else:
        #print(f'overlap {a} {b}')
        link[(a, b)] += w

edges = [(a, b, w) for (a, b), w in link.items()]
algo = FortdFulkerson(edges, start, end, max_node_num=n, max_edge_num=m)
print(algo.getMaxFlow()[0])



皓首不倦
20小时前


'''
求最小割和求最大流是等价的,直接用Dinic求最大流即可
'''

from typing import List
from collections import deque

class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    #返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num*2 + 1)            # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num*2 + 1)            # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num*2 + 1)           # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)              # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)            # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)            # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度
        orig_flow = [0] * (self.max_edge_num + 1)       # 原图中有向边的流量

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False


        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]     # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node]+1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx^1], flow = f[idx]-t, f[idx^1]+t, flow+t

                    # 更新原图边的流量
                    if self.edges[idx>>1][0] == node:
                        orig_flow[idx>>1] += t
                    else:
                        orig_flow[idx>>1] -= t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow, [(self.edges[i][0], self.edges[i][1], orig_flow[i], self.edges[i][2]) for i in range(len(self.edges))]

n, m, start, end = map(int, input().split())
link = {}
for _ in range(m):
    a, b, w = map(int, input().split())

    if (a, b) not in link:
        link[(a, b)] = w
    else:
        #print(f'overlap {a} {b}')
        link[(a, b)] += w

edges = [(a, b, w) for (a, b), w in link.items()]
algo = FortdFulkerson(edges, start, end, max_node_num=n, max_edge_num=m)
print(algo.getMaxFlow()[0])



活动打卡代码 AcWing 2237. 猪

皓首不倦
22小时前
from collections import deque

class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow




m, n = map(int, input().split())
X = list(map(int, input().split()))

S, T = n+1, n+2

edges = []
visit = [[] for i in range(m)]      # visit[idx]记录idx号猪舍被那些顾客打开过
for i in range(1, n+1):
    arr = list(map(int, input().split()))
    buy_cnt = arr[-1]
    for house_idx in arr[1:-1]:
        house_idx -= 1

        if len(visit[house_idx]) == 0:
            edges.append((S, i, X[house_idx]))
        else:
            for cus_idx in visit[house_idx]:
                edges.append((cus_idx, i, 0x7fffffff))

        visit[house_idx].append(i)
    edges.append((i, T, buy_cnt))

print(FortdFulkerson(edges, S, T, n+2, len(edges)).getMaxFlow())



皓首不倦
22小时前

acwing2237.png



from collections import deque

class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow




m, n = map(int, input().split())
X = list(map(int, input().split()))

S, T = n+1, n+2

edges = []
visit = [[] for i in range(m)]      # visit[idx]记录idx号猪舍被那些顾客打开过
for i in range(1, n+1):
    arr = list(map(int, input().split()))
    buy_cnt = arr[-1]
    for house_idx in arr[1:-1]:
        house_idx -= 1

        if len(visit[house_idx]) == 0:
            edges.append((S, i, X[house_idx]))
        else:
            for cus_idx in visit[house_idx]:
                edges.append((cus_idx, i, 0x7fffffff))

        visit[house_idx].append(i)
    edges.append((i, T, buy_cnt))

print(FortdFulkerson(edges, S, T, n+2, len(edges)).getMaxFlow())