コード
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int W = nextInt();
int N = nextInt();
int[] J = new int[N];
for (int i = 0; i < J.length; i++) {
J[i] = nextInt();
}
int M = nextInt();
int[] C = new int[M];
for (int i = 0; i < C.length; i++) {
C[i] = nextInt();
}
MaximumFlow maximumFlow = new MaximumFlow(M + N + 2, N + M, N + M + 1);
for (int i = 0; i < N; i++) {
maximumFlow.addEdge(N + M, i, J[i]);
}
for (int j = 0; j < M; j++) {
maximumFlow.addEdge(N + j, N + M + 1, C[j]);
}
for (int j = 0; j < M; j++) {
int Q = nextInt();
boolean[] hate = new boolean[N];
for (int q = 0; q < Q; q++) {
hate[nextInt() - 1] = true;
}
for (int i = 0; i < N; i++) {
if (!hate[i]) {
maximumFlow.addEdge(i, N + j, J[i]);
}
}
}
int maximum = maximumFlow.fordFulkerson();
if (maximum >= W) {
System.out.println("SHIROBAKO");
} else {
System.out.println("BANSAKUTSUKITA");
}
}
static int nextInt() {
int c;
try {
c = System.in.read();
while (c != '-' && (c < '0' || c > '9'))
c = System.in.read();
if (c == '-')
return -nextInt();
int res = 0;
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = System.in.read();
}
return res;
} catch (IOException e) {
TODO
e.printStackTrace();
}
return -1;
}
}
class MaximumFlow {
public static final int INF = 100000000;
int V;
int source;
int sink;
ArrayList<Edge>[] graph;
boolean[] used;
@SuppressWarnings("unchecked")
public MaximumFlow(int V, int source, int sink) {
this.V = V;
this.source = source;
this.sink = sink;
graph = new ArrayList[V];
for (int i = 0; i < V; i++) {
graph[i] = new ArrayList<Edge>();
}
used = new boolean[V];
}
public void addEdge(int from, int to, int cap) {
graph[from].add(new Edge(to, cap, graph[to].size()));
graph[to].add(new Edge(from, 0, graph[from].size() - 1));
}
public int fordFulkerson() {
int flow = 0;
while (true) {
Arrays.fill(used, false);
int f = dfsFF(source, sink, INF);
if (f == 0) {
break;
}
flow += f;
}
return flow;
}
private int dfsFF(int from, int to, int flow) {
if (from == to) {
return flow;
}
used[from] = true;
for (Edge edge : graph[from]) {
if (used[edge.to] || edge.cap <= 0) {
continue;
}
int d = dfsFF(edge.to, to, Math.min(flow, edge.cap));
if (d > 0) {
edge.cap -= d;
graph[edge.to].get(edge.rev).cap += d;
return d;
}
}
return 0;
}
class Edge {
int to;
int cap;
int rev;
public Edge(int to, int cap, int rev) {
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
}