'''
转换成有源点,有汇点,流量上下界约束的最小流模型
用Dinic算法求解即可
'''
INF = 0x7fffffffffffffff
from collections import deque
class FortdFulkerson:
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
def Dinic(self, rev_edge_w = None):
e = [-1] * (self.max_edge_num*2 + 1)
f = [-1] * (self.max_edge_num*2 + 1)
ne = [-1] * (self.max_edge_num*2 + 1)
h = [-1] * (self.max_node_num + 1)
dis = [-1] * (self.max_node_num + 1)
cur = [-1] * (self.max_node_num + 1)
orig_flow = [0] * (self.max_edge_num + 1)
idx = 0
for i, (a, b, w) in enumerate(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
if rev_edge_w is not None:
f[idx] = rev_edge_w[i]
idx += 1
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
def dfs(node, limit) -> int:
if node == self.end_node:
return limit
flow = 0
idx = cur[node]
while idx != -1 and flow < limit:
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():
max_flow += dfs(self.source_node, INF)
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))]
from collections import Counter
n, m, S, T = map(int, input().split())
SS, TT = n+1, n+2
edges = []
L = []
sum1, sum2 = Counter(), Counter()
for _ in range(m):
a, b, l, u = map(int, input().split())
edges.append((a, b, u-l))
L.append(l)
sum1[b] += l
sum2[a] += l
edges.append((T, S, INF))
sum1[S] += 0
sum2[T] += 0
for node in range(1, n+1):
v1 = 0 if node not in sum1 else sum1[node]
v2 = 0 if node not in sum2 else sum2[node]
if v1 > v2:
edges.append((SS, node, v1-v2))
else:
edges.append((node, TT, v2-v1))
algo = FortdFulkerson(edges, SS, TT, max_node_num=n+2, max_edge_num=len(edges))
ans = algo.Dinic()
F1 = 0
flag = True
for a, b, f, w in ans[1]:
if a == SS and f != w:
flag = False
break
if w == INF:
F1 = f
if not flag:
print('No Solution')
else:
e = []
rev_w = []
for a, b, f, w in ans[1]:
if a >= 1 and a <= n and b >= 1 and b <= n and w != INF and w-f > 0:
e.append((a, b, w-f))
rev_w.append(f)
algo = FortdFulkerson(e, T, S, max_node_num=n, max_edge_num=len(e))
ans = algo.Dinic(rev_w)
F2 = ans[0]
ans = F1 - F2
print(ans)