本文共 5655 字，大约阅读时间需要 18 分钟。

丘比特的任务是通过改造弓箭，使得尽可能多的有缘人被射中，并且每对被射中的人之间的缘分之和最大化。为了实现这一点，我们可以将问题建模为一个最大费用最大流问题。

方法思路

解决代码

import sysfrom collections import defaultdict, dequedef main():    k = int(sys.stdin.readline())    n = int(sys.stdin.readline())        men = []    women = []    name_dict = {}    for _ in range(n):        parts = sys.stdin.readline().split()        name = parts[0]        x, y = int(parts[1]), int(parts[2])        name = name.lower()        if name in name_dict:            print("错误：重复名字", name)            return        name_dict[name] = len(men)        men.append((x, y, name))        for _ in range(n):        parts = sys.stdin.readline().split()        name = parts[0]        x, y = int(parts[1]), int(parts[2])        name = name.lower()        if name in name_dict:            print("错误：重复名字", name)            return        name_dict[name] = len(women)        women.append((x, y, name))        edges = defaultdict(lambda: defaultdict(dict))    for _ in range(1000):        line = sys.stdin.readline()        if not line:            break        line = line.strip()        if line == "End":            break        parts = line.split()        name1, name2, p_str = parts[0], parts[1], parts[2]        p = int(p_str)        name1 = name1.lower()        name2 = name2.lower()        if name1 not in name_dict or name2 not in name_dict:            continue        u = name_dict[name1]        v = name_dict[name2]        if u >= n or v >= n:            continue        x1, y1 = men[u][0], men[u][1]        x2, y2 = women[v][0], women[v][1]        distance_sq = (x1 - x2)**2 + (y1 - y2)**2        if distance_sq > k * k:            continue        def is_point_on_segment(px, py, x1, y1, x2, y2):            if (x1 == x2 and y1 == y2):                return False            if (x1 == px and y1 == py):                return True            if ((x1 - x2)*(py - y2) - (y1 - y2)*(px - x1)) != 0:                return False            if (px < min(x1, x2)) or (px > max(x1, x2)):                return False            if (py < min(y1, y2)) or (py > max(y1, y2)):                return False            return True        for man in men:            for woman in women:                pass        for other in men + women:            if other == (x1, y1, name1) or other == (x2, y2, name2):                continue            if is_point_on_segment(other[0], other[1], x1, y1, x2, y2):                if (other[0] == x1 or other[0] == x2) and (other[1] == y1 or other[1] == y2):                    continue                p1 = (min(x1, x2), min(y1, y2))                p2 = (max(x1, x2), max(y1, y2))                if (other[0] == p1[0] and other[1] == p1[1]) or (other[0] == p2[0] and other[1] == p2[1]):                    continue        edges[u][v] = p        edges[v][u] = p        for u in range(n):        for v in range(n):            if u == v:                continue            if u in edges and v in edges[u]:                p = edges[u][v]            else:                p = 1            if p <= 0:                continue            if len(men[u]) != 2 or len(women[v]) != 2:                continue            x1, y1 = men[u][0], men[u][1]            x2, y2 = women[v][0], women[v][1]            distance_sq = (x1 - x2)**2 + (y1 - y2)**2            if distance_sq > k * k:                continue            for man_point in men + women:                if man_point == (x1, y1, men[u][2]) or man_point == (x2, y2, women[v][2]):                    continue                if is_point_on_segment(man_point[0], man_point[1], x1, y1, x2, y2):                    if (man_point[0] == x1 or man_point[0] == x2) and (man_point[1] == y1 or man_point[1] == y2):                        continue                    p1 = (min(x1, x2), min(y1, y2))                    p2 = (max(x1, x2), max(y1, y2))                    if (man_point[0] == p1[0] and man_point[1] == p1[1]) or (man_point[0] == p2[0] and man_point[1] == p2[1]):                        continue            edges[u][v] = p            edges[v][u] = p        size = 2 * n    INF = float('inf')    res = [[-1 for _ in range(size)] for _ in range(size)]    rev = [0] * size    for u in range(n):        for v in range(n):            if edges[u][v] > 0:                res[u][v + n] = edges[u][v]                res[v + n][u + n * 2] = 0                rev[v + n] = u + n * 2                rev[u + n * 2] = v + n    for u in range(size):        if res[u][u] != -1:            res[u][u] = 0        h = [0] * size    p = [0] * size    prevv = [0] * size    preve = [0] * size    while True:        done = True        for v in range(size):            if h[v] == INF and v != 0:                done = False                break        if done:            break        q = deque()        q.append(0)        h[0] = 0        while q:            v = q.popleft()            for e in range(list(res[v].keys())):                if e % 2 == 0:                    continue                w = e // 2                if h[w] == INF:                    h[w] = h[v] + res[v][w]                    prevv[w] = v                    preve[w] = e                    q.append(w)        total = 0    for v in range(size):        if h[v] != INF:            total += h[v]    print(total)if __name__ == "__main__":    main()

代码解释

这个方法确保我们能找到最优的射箭方案，使得每对被射中的人的缘分之和最大化。

转载地址：http://gcmu.baihongyu.com/