'''
转成二分图的最小点权值和覆盖点集问题求解
'''
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
# 获取最小割的划分方案,返回最小割容量以及两个列表,第一个列表为和源点在一个集合中的所有点,第二个列表是和汇点在同一个集合中的所有点
def getMinCut(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
min_cut_cap = 0
while bfs():
# 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
min_cut_cap += dfs(self.source_node, 0x7fffffff)
visit = [0] * (self.max_node_num + 1)
def travel(cur):
visit[cur] = 1
idx = h[cur]
while idx != -1:
next_node = e[idx]
if visit[next_node] == 0 and f[idx] > 0:
travel(next_node)
idx = ne[idx]
travel(self.source_node)
s_nodes = [node for node in range(1, self.max_node_num+1) if visit[node] == 1]
t_nodes = [node for node in range(1, self.max_node_num+1) if visit[node] == 0]
return min_cut_cap, s_nodes, t_nodes
n, m = map(int, input().split())
w_pos = [0] + list(map(int, input().split()))
w_neg = [0] + list(map(int, input().split()))
# part1 点范围为1 - n part2点范围为n+1 - 2n
edges = []
S, T = 2*n+1, 2*n+2
for node in range(1, n+1):
edges.append((S, node, w_neg[node]))
edges.append((node+n, T, w_pos[node]))
for _ in range(m):
a, b = map(int, input().split())
edges.append( (a, b+n, 0x7fffffff) )
min_cut_cap, ss, tt = FortdFulkerson(edges, S, T, 2*n+2, len(edges)).getMinCut()
print(min_cut_cap)
pos_nodes = []
neg_nodes = []
for node in ss:
if node >= n+1 and node <= 2*n:
pos_nodes.append(node-n)
for node in tt:
if node >= 1 and node <= n:
neg_nodes.append(node)
print(len(pos_nodes) + len(neg_nodes))
for node in pos_nodes:
print(f'{node} +')
for node in neg_nodes:
print(f'{node} -')