"""共同支出构造模型。金额单位为元,所有输入使分配恰好到分,无提前舍入。""" from collections import deque from datetime import date, timedelta from fractions import Fraction from pathlib import Path import json def allocate(amount, weights): total = sum(weights) assert total > 0 and amount >= 0 and min(weights) >= 0 result = [Fraction(amount) * w / total for w in weights] assert all((x * 100).denominator == 1 for x in result) return [int(x) if x.denominator == 1 else f'{int(x*100)//100}.{int(x*100)%100:02d}' for x in result] def netting(names, edges): net = dict.fromkeys(names, 0) for a, b, amount in edges: net[a] -= amount net[b] += amount pending = net.copy() transfers = [] while any(x < 0 for x in pending.values()): debtor = min(names, key=lambda n: (pending[n], names.index(n))) creditor = max(names, key=lambda n: (pending[n], -names.index(n))) amount = min(-pending[debtor], pending[creditor]) transfers.append([debtor, creditor, amount]) pending[debtor] += amount pending[creditor] -= amount checks = [] for n in names: incoming = sum(v for a, b, v in transfers if b == n) outgoing = sum(v for a, b, v in transfers if a == n) checks.append([n, net[n], incoming, outgoing, net[n] - incoming + outgoing]) return {'net': net, 'transfers': transfers, 'checks': checks, 'net_sum': sum(net.values()), 'payment_total': sum(r[2] for r in transfers), 'original_gross': sum(r[2] for r in edges)} def bounded(cost, caps, order, floor=400): shares = [min(floor, cap) for cap in caps] assert sum(shares) <= cost remaining = cost - sum(shares) steps = [['起始', *shares, remaining]] for i in order: add = min(remaining, caps[i] - shares[i]) shares[i] += add remaining -= add steps.append([['甲', '乙', '丙'][i], *shares, remaining]) return {'shares': shares, 'steps': steps, 'cap_sum': sum(caps), 'gap': remaining, 'feasible': remaining == 0} def flow(supply, demand, allowed): """Edmonds–Karp整数最大流;本例仅允许付款者直达收款者,无中转。""" capacity = {} def edge(a, b, c): capacity[a, b] = c capacity.setdefault((b, a), 0) total = sum(supply.values()) assert total == sum(demand.values()) for n, v in supply.items(): edge('源', n, v) for a, b in allowed: edge(a, b, total) for n, v in demand.items(): edge(n, '汇', v) residual = capacity.copy() sent = 0 while True: parent = {'源': None} q = deque(['源']) while q and '汇' not in parent: a = q.popleft() for x, b in residual: if x == a and residual[x, b] > 0 and b not in parent: parent[b] = a q.append(b) if '汇' not in parent: break v, b = total, '汇' while parent[b] is not None: a = parent[b]; v = min(v, residual[a, b]); b = a b = '汇' while parent[b] is not None: a = parent[b]; residual[a, b] -= v; residual[b, a] += v; b = a sent += v reachable = {'源'} changed = True while changed: changed = False for (a, b), c in residual.items(): if a in reachable and c > 0 and b not in reachable: reachable.add(b); changed = True cut = [[a, b, c] for (a, b), c in capacity.items() if c and a in reachable and b not in reachable] transfers = [[a, b, capacity[a, b] - residual[a, b]] for a, b in allowed] checks = [] for n in list(supply) + list(demand): incoming = sum(v for a, b, v in transfers if b == n) outgoing = sum(v for a, b, v in transfers if a == n) target = demand.get(n, 0) - supply.get(n, 0) checks.append([n, target, incoming, outgoing, target - incoming + outgoing]) return {'transfers': transfers, 'checks': checks, 'flow': sent, 'gap': total - sent, 'feasible': sent == total, 'reachable_residual': sorted(reachable), 'cut': cut, 'cut_capacity': sum(x[2] for x in cut)} def build(): out = {} expenses = [['房费', 2400, [1, 1], [2400, 0]], ['餐食', 900, [2, 1], [0, 900]], ['甲用品', 240, [1, 0], [240, 0]], ['交通', 300, [1, 1], [0, 300]]] matrix = [[label, cost, *allocate(cost, w), *paid] for label, cost, w, paid in expenses] people = [[n, sum(r[2+i] for r in matrix), sum(r[4+i] for r in matrix)] for i, n in enumerate(['甲', '乙'])] summary = [[n, share, paid, paid-share] for n, share, paid in people] alt = [r.copy() for r in matrix] alt[1][2:4] = allocate(expenses[1][1], [1, 1]) out['DJ4-111'] = {'input': {'expenses': expenses}, 'matrix': matrix, 'summary': summary, 'net_sum': sum(r[3] for r in summary), 'equal_meal_summary': [[n, sum(r[2+i] for r in alt), paid, paid-sum(r[2+i] for r in alt)] for i, (n, _, paid) in enumerate(people)], 'wrong_equal_all': [[n, sum(r[1] for r in matrix)//2, paid-sum(r[1] for r in matrix)//2] for n,_,paid in people]} names = list('ABCDEF') edges = [['A','B',120],['A','C',80],['B','D',70],['C','D',30], ['D','E',60],['E','F',40],['F','A',150],['C','F',20]] alt = [r.copy() for r in edges]; alt[3][2] = 60 out['DJ4-112'] = {'input': {'names': names, 'owed_edges': edges, 'changed_C_D': 60}, 'base': netting(names, edges), 'changed': netting(names, alt)} items = [['米',120,[1,1,1],[120,0,0]], ['水果',90,[1,1,0],[90,0,0]], ['甲用品',60,[1,0,0],[60,0,0]], ['乙用品',30,[0,1,0],[30,0,0]], ['丙用品',90,[0,0,1],[0,0,90]]] rows = [[n, v, *[str(Fraction(w, sum(ws))) for w in ws], *allocate(v, ws), *paid] for n,v,ws,paid in items] summary = [[n, sum(r[5+i] for r in rows), sum(r[8+i] for r in rows)] for i,n in enumerate('甲乙丙')] out['DJ4-113'] = {'input': {'items':items}, 'items':rows, 'summary': [[n, share, paid, paid-share] for n,share,paid in summary], 'category_totals': {'共同':sum(v for _,v,w,_ in items if sum(x>0 for x in w)>1), '专用':sum(v for _,v,w,_ in items if sum(x>0 for x in w)==1)}, 'wrong_equal_all': [[n, sum(x[1] for x in items)//3, sum(x[1] for x in items)//3-share] for n,share,paid in summary]} opening = [180,120,0]; contributions = [1000,700,500]; cost = 1200 shares = allocate(cost,[5,3,2]) carry = [[n,opening[i],contributions[i],shares[i],opening[i]+contributions[i]-shares[i]] for i,n in enumerate('甲乙丙')] extra = allocate(300,[5,3,2]) out['DJ4-114'] = {'input':{'opening':opening,'contributions':contributions,'cost':cost,'weights':[5,3,2],'extra_cost':300}, 'carry':carry,'cash':sum(r[4] for r in carry), 'extra_cost_carry':[[r[0],r[4],extra[i],r[4]-extra[i]] for i,r in enumerate(carry)], 'missing_B_contribution':[[r[0],r[4]-(200 if i==1 else 0)] for i,r in enumerate(carry)], 'wrong_redistributed_balance':allocate(sum(r[4] for r in carry),[5,3,2])} original = allocate(900,[5,3,2]); refunds = allocate(180,[5,3,2]); targeted = [0,120,60] out['DJ4-115'] = {'input':{'cost':900,'weights':[5,3,2],'paid':[900,0,0], 'refund':180,'refund_receiver':'甲','targeted_refund':targeted,'partial_B_paid':200}, 'original':[[n,original[i],900 if i==0 else 0,(900 if i==0 else 0)-original[i]] for i,n in enumerate('甲乙丙')], 'settlement':[['乙','甲',original[1]],['丙','甲',original[2]]], 'increment':[[n,original[i],refunds[i],refunds[i] if i else 0,original[i]-refunds[i]] for i,n in enumerate('甲乙丙')], 'targeted':[[n,targeted[i],original[i]-targeted[i]] for i,n in enumerate('甲乙丙')], 'partial_B':{'old_unpaid':original[1]-200,'refund_share':refunds[1],'net_still_pay':original[1]-200-refunds[1]}} intervals = [['甲','2026-09-01','2026-10-01'],['乙','2026-09-01','2026-09-16'],['丙','2026-09-16','2026-10-01']] days = [(date.fromisoformat(e)-date.fromisoformat(s)).days for n,s,e in intervals] fixed = allocate(1800,[1,1,1]); variable = allocate(600,days); alt = allocate(1800,days) daily = [] start = date(2026,9,1) for j in range(30): d = start+timedelta(days=j) active = [n for n,s,e in intervals if date.fromisoformat(s)<=d