첫째 줄에 살 수 있는 책의 최대 개수를 출력한다.
입력
4 4
3 2 4 2
5 3 2 1
0 1 1 0
1 0 1 2
2 1 1 1
0 0 2 0
출력
8
구현
class MaximumFlow {
class Edge {
int to, capacity;
Edge rev;
Edge(int to, int capacity) {
this.to = to;
this.capacity = capacity;
}
}
int n, source, sink;
ArrayList<Edge>[] graph;
boolean[] check;
MaximumFlow(int n, int source, int sink) {
this.n = n;
this.source = source;
this.sink = sink;
graph = new ArrayList[n];
check = new boolean[n];
for (int i=0; i<n; i++) {
graph[i] = new ArrayList<Edge>();
}
}
void add_edge(int u, int v, int cap) {
Edge ori = new Edge(v, cap);
Edge rev = new Edge(u, 0);
ori.rev = rev;
rev.rev = ori;
graph[u].add(ori);
graph[v].add(rev);
}
void add_edge_from_source(int v, int cap) {
add_edge(source, v, cap);
}
void add_edge_to_sink(int u, int cap) {
add_edge(u, sink, cap);
}
int bfs() {
boolean[] check = new boolean[n];
int[] from1 = new int[n];
int[] from2 = new int[n];
for (int i=0; i<n; i++) {
from1[i] = from2[i] = -1;
}
Queue<Integer> q = new LinkedList<>();
q.add(source);
check[source] = true;
while (!q.isEmpty()) {
int x = q.remove();
for (int i=0; i<graph[x].size(); i++) {
Edge e = graph[x].get(i);
if (e.capacity > 0 && !check[e.to]) {
q.add(e.to);
check[e.to] = true;
from1[e.to] = x;
from2[e.to] = i;
}
}
}
if (!check[sink]) {
return 0;
}
int x = sink;
int c = graph[from1[x]].get(from2[x]).capacity;
while (from1[x] != -1) {
if (c > graph[from1[x]].get(from2[x]).capacity) {
c = graph[from1[x]].get(from2[x]).capacity;
}
x = from1[x];
}
x = sink;
while (from1[x] != -1) {
Edge e = graph[from1[x]].get(from2[x]);
e.capacity -= c;
e.rev.capacity += c;
x = from1[x];
}
return c;
}
int flow() {
int ans = 0;
while (true) {
Arrays.fill(check, false);
int f = bfs();
if (f == 0) break;
ans += f;
}
return ans;
}
}
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
MaximumFlow mf = new MaximumFlow(n+m+2, n+m, n+m+1);
for (int i=0; i<n; i++) {
int x = sc.nextInt();
mf.add_edge_to_sink(m+i,x);
}
for (int i=0; i<m; i++) {
int x = sc.nextInt();
mf.add_edge_from_source(i,x);
}
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
int x = sc.nextInt();
mf.add_edge(i,j+m,x);
}
}
System.out.println(mf.flow());
}
}