#region ZIPPER using System; using System.Collections.Generic; using System.Collections; using System.Linq; using System.Text; using sc = Scanner; using ci = CharInterpreter; //using System.Numerics; //using Geometry; //using gl = Geometry.GeometryLibrary; using grl = GraphLibrary; class Program { static void Main(string[] args) { Solver solver = new Solver(); solver.Solve(); #if DEBUG System.Console.WriteLine("続行するには何かキーを押してください..."); System.Console.ReadKey(); #endif } } /// /// 標準入力読み取り支援,自作(某最速の人を参考) /// #endregion ZIPPER public class Solver { #region IGNORE_ME public Solver() { //こんすとらくたん きにしなくてよろしい } #endregion IGNORE_ME public int MOD = 1000000007;//10^9 + 7 public void Solve() { int w = sc.NextInt(); int n = sc.NextInt(); int[] jjj = sc.NextIntArray(); int m = sc.NextInt(); int[] c = sc.NextIntArray(); List[] G = new List[2+n+m]; int s = n+m;//これの仲介変数ないとコーディングの辛みがおおい int t = s+1;// for (int i = 0; i < 2 + n + m ; i++) { G[i] = new List(); } int[] qx; for (int i = 0; i < m; i++) { qx = sc.NextIntArray(); bool[] canDispatch = Enumerable.Repeat(true,n).ToArray(); for (int j = 1; j < qx[0]+1; j++) { canDispatch[qx[j]-1] = false; } for (int j = 0; j < n; j++) { if (canDispatch[j])grl.AddEdge(ref G,j,n+i,jjj[j]); } } for (int i = 0; i = 0 ? "SHIROBAKO":"BANSAKUTUKITA"); #if DEBUG Console.WriteLine("t");//local check #endif } } public static class GraphLibrary { public struct Edge { /// /// 最大流の場合は逆辺 rev /// public int Rev; public int To; /// /// 最大流の場合は容量 /// public int Cap; public Edge(int to, int cap, int rev) { this.To = to; this.Cap = cap; this.Rev = rev; } } public class Graph { public List[] G; /// /// 頂点のインデックスは 0 ~ v-1; /// /// 頂点数 public Graph(int v) { G = new List[v]; for (int i = 0; i < G.Length; i++) { G[i] = new List(); } } public void AddEdge(Edge edge) { G[edge.Rev].Add(edge); } } #region UTILITY static bool IsInfinity(int a) { return a == int.MaxValue; } #endregion UTILITY /// /// 最短経路長を求める /// /// 点の数 /// 始点 0 ~ v-1 /// 辺の情報 /// d[i]: sからiへの最短経路長 public static int[] BellmanFord(int v, int s, Edge[] ed) { int[] d = new int[v]; for (int i = 0; i < v; i++) d[i] = int.MaxValue; d[s] = 0; while (true) { bool update = false; for (int i = 0; i < ed.Length; i++) { Edge e = ed[i]; if (!IsInfinity(d[e.Rev]) && !IsInfinity(e.Cap) && d[e.To] > d[e.Rev] + e.Cap) { d[e.To] = d[e.Rev] + e.Cap; update = true; } } if (!update) break; } return d; } /// /// 負の閉路が存在するかどうか /// /// 頂点の数 /// 辺の集合 /// 負の閉路が存在するかどうか public static bool DoesHaveNegativeLoop(int v, Edge[] ed) { int[] d = new int[v]; for (int i = 0; i < v; i++) { for (int j = 0; j < ed.Length; j++) { Edge e = ed[j]; if (d[e.To] > d[e.Rev] + e.Cap) { d[e.To] = d[e.Rev] + e.Cap; if (i == v - 1) return true;//この時の更新があったら閉路があるらしい } } } return false; } /// /// 負の閉路がある場合、無視できるかどうか /// 始点から負の閉路へ到達することができない /// /// /// /// /// public static bool DontReachNegativeLoop(int v, int s, Edge[] ed) { Edge[] connectedNodesChecker = new Edge[ed.Length]; for (int i = 0; i < ed.Length; i++) { connectedNodesChecker[i] = new Edge(ed[i].Rev, ed[i].To, 1); } int[] d = BellmanFord(v, s, connectedNodesChecker); HashSet canReachNodesFromS = new HashSet(); for (int i = 0; i < v; i++) if (!IsInfinity(d[i]))canReachNodesFromS.Add(i); for (int i = 0; i < ed.Length; i++) if (canReachNodesFromS.Contains(ed[i].Rev)) connectedNodesChecker[i].Cap = ed[i].Cap; return DoesHaveNegativeLoop(v,connectedNodesChecker); } /// /// 最短経路長を求める /// /// 二次元マップ /// d[i][j]]: iからjへの最短経路長 public static int[][] WarshallFloyd(int[][] graph) { int[][] d = new int[graph.Length][]; for (int i = 0; i < d.Length; i++) d[i] = new int[graph[0].Length]; for (int k = 0; k < graph.Length; k++) { for (int i = 0; i < graph.Length; i++) { for (int j = 0; j < graph.Length; j++) { if (!IsInfinity(d[i][k]) && !IsInfinity(d[k][j])) { d[i][j] = Math.Min(d[i][j], d[i][k] + d[k][j]); } } } } return d; } /// /// 連結なグラフの最小全域木を求める /// /// 頂点の数 /// 辺の集合 to, from は気にしなくてよい /// 最小全域木の重み public static int Kruskal(int v, Edge[] ed) { Array.Sort(ed, (a, b) => { return a.Cap - b.Cap; }); UnionFindTree uf = new UnionFindTree(v); int res = 0; for (int i = 0; i < ed.Length; i++) { Edge e = ed[i]; if (!uf.Same(e.To, e.Rev)) { uf.Unite(e.To, e.Rev); res += e.Cap; } } return res; } public static void AddEdge(ref List[] G, int from, int to, int cap) { G[from].Add(new Edge(to, cap, G[to].Count)); G[to].Add(new Edge(from, 0, G[from].Count - 1)); } public static int MaxFlow(List[] G, int v , int s, int t) { MaxFlowSolver solver = new MaxFlowSolver(); return solver.MaxFlow(G, v, s, t); } private class MaxFlowSolver { private List[] G; private int[] Level; private int[] Iter; public MaxFlowSolver() { } void BFSForLevelSetting(int s) { Queue que = new Queue(); for (int i = 0; i < Level.Length; i++) Level[i] = -1; Level[s] = 0; que.Enqueue(s); while (que.Count != 0) { int v = que.Dequeue(); for (int i = 0; i < G[v].Count; i++) { if (G[v][i].Cap > 0 && Level[G[v][i].To] < 0) { Level[G[v][i].To] = Level[v] + 1; que.Enqueue(G[v][i].To); } } } } private int DFSForGainPass(int v, int t, int f) { if (v == t) return f; for (int i = Iter[v]; i < G[v].Count; i++) { Edge e = G[v][i]; if (e.Cap > 0 && Level[v] < Level[e.To]) { int d = DFSForGainPass(e.To, t, Math.Min(f, e.Cap)); if (d > 0) { G[v][i] = new Edge(e.To, e.Cap - d, e.Rev); G[e.To][e.Rev] = new Edge(G[e.To][e.Rev].To, G[e.To][e.Rev].Cap + d, G[e.To][e.Rev].Rev);; return d; } } } return 0; } public int MaxFlow(List[] G, int v,int s, int t) { this.G = (List[])G.Clone(); this.Level = Enumerable.Repeat(-1, v).ToArray(); this.Iter = new int[v]; int flow = 0; for (;;) { BFSForLevelSetting(s); if (Level[t] < 0) return flow; for (int i = 0; i < Iter.Length; i++) Iter[i] = 0; int f; while (true) { f = DFSForGainPass(s, t, int.MaxValue); if (f == 0) break; flow += f; } } } } #region SUPPORT_INNER_CLASS /// /// ダイクストラ法に使うつもりの優先度付きキュー /// インナークラス /// private class PriorityQueueForGL { int[] array; int count = 0; Comparison comparison; // intに対する比較方向を示すデリゲート, (a,b)のとき返り値intに a_int - b_int (a > b) なら昇順,逆なら降順 public void SetOptionData(Comparison comparison, int MaxCount) { this.comparison = comparison; array = new int[MaxCount]; count = 0; } /// /// ヒープ化されている配列リストに新しい要素を追加する。 /// /// 対象の配列リスト private void PushHeap(int elem) { int n = count; count++; array[n] = elem; while (n != 0) { int i = (n - 1) / 2; // 親と値を入れ替え if (comparison(array[n], array[i]) < 0) { int tmp = array[n]; array[n] = array[i]; array[i] = tmp; } n = i; } } /// /// ヒープから指定した値を削除する。 /// /// 対象の配列リスト private int PopHeap() { if (count == 0) throw new IndexOutOfRangeException("要素が0のキューに要素を取り出す命令がおこなわれました"); int n = count - 1; int returnItem = (int)array[0]; array[0] = array[n]; array[n] = 0; count--; for (int i = 0, j; (j = 2 * i + 1) < n; ) { // 値の大きい方の子を選ぶ if ((j != n - 1) && (comparison((int)array[j], (int)array[j + 1]) > 0)) j++; // 子と値を入れ替え if (comparison((int)array[i], (int)array[j]) > 0) { int tmp = (int)array[j]; array[j] = array[i]; array[i] = tmp; } i = j; } return returnItem; } /// /// 要素のプッシュ. /// /// 挿入したい要素 public void Push(int elem) { PushHeap(elem); } /// /// 要素をポップ.出したデータはコレクションの中から消える /// /// public int Pop() { return PopHeap(); } /// /// 要素を全て消去する /// public void Clear() { for (int i = 0; i < array.Length; i++) array[i] = 0; } } /// /// UF木、蟻本より /// class UnionFindTree { int[] Par; int[] Rank; /// /// nの要素数を管理するUF木 /// /// public UnionFindTree(int n) { this.Par = new int[n]; this.Rank = new int[n]; for (int i = 0; i < n; i++) { Par[i] = i; } } /// /// 木の根を求める /// /// /// private int Find(int x) { if (Par[x] == x) return x; else { Par[x] = Find(Par[x]); return Par[x]; } } /// /// xとyの属する集合を併合 /// /// /// public void Unite(int x, int y) { x = Find(x); y = Find(y); if (x == y) return; if (Rank[x] < Rank[y]) { Par[x] = y; } else { Par[y] = x; if (Rank[x] == Rank[y]) Rank[x]++; } } /// /// xとyが同じ集合に属するか否か /// /// /// /// public bool Same(int x, int y) { return Find(x) == Find(y); } } #endregion SUPPORT_INNER_CLASS } #region STANDARD_READER public static class Scanner { public static string NextString() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return tmp; } public static int NextInt() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return int.Parse(tmp); } public static long NextLong() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return long.Parse(tmp); } public static double NextDouble() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return double.Parse(tmp); } public static string[] NextStrArray() { return Console.ReadLine().Split(' '); } public static int[] NextIntArray() { string[] s = NextStrArray(); int[] a = new int[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = int.Parse(s[i]); } return a; } public static long[] NextLongArray() { string[] s = NextStrArray(); long[] a = new long[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = long.Parse(s[i]); } return a; } public static double[] NextDoubleArray() { string[] s = NextStrArray(); double[] a = new double[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = double.Parse(s[i]); } return a; } } /// /// 二次元グリッドなどの文字列で与えられたマップなどで、 /// 手軽にデータ変換を適用するためのクラス /// public static class CharInterpreter { /// /// 変換用辞書 /// private static Dictionary MapToInt = new Dictionary(); /// /// 変換法則を追加する /// /// char文字 /// 対応する整数値 public static void AddCorrespondence(char c,int i) { MapToInt.Add(c,i); } /// /// 文字列に対して、対応付けされた /// 例外処理をしていないので注意 /// /// 対応対応がなかった場合はバグる;; public static int Inquiry(char c) { int ret = 0; MapToInt.TryGetValue(c, out ret); return ret; } /// /// 指定された変換法則の元でint[,]の二次元平面を生成する /// 対応関係がない場合の例外処理をしていないので注意 /// /// 配列の各文字列の長さが全て同じでないとうまく作動しないので注意 /// int[ field.length , field[0].length]型の配列 public static int[,] GenerateSquareField(string[] field) { int[,] ret = new int[field.Length, field[0].Length]; for (int i = 0; i < field.Length; i++) { for (int j = 0; j < field[0].Length; j++) { MapToInt.TryGetValue(field[i][j], out ret[i, j]); } } return ret; } } #endregion STANDARD_READER /* Ford Fulkerson public static int MaxFlow(List[] G, int v , int s, int t) { MaxFlowSolver solver = new MaxFlowSolver(G, v); return solver.MaxFlow(s, t); } private class MaxFlowSolver { private List[] G; private bool[] Used; public MaxFlowSolver(List[] G, int v) { this.G = G; this.Used = new bool[G.Length]; } private int Dfs(int v, int t, int f) { if (v == t) return f; Used[v] = true; for (int i = 0; i < G[v].Count; i++) { Edge e = G[v][i]; if (!Used[e.To] && e.Cap > 0) { int d = Dfs(e.To, t, Math.Min(f, e.Cap)); if (d > 0) { G[v][i] = new Edge(e.To, e.Cap - d, e.Rev); G[e.To][e.Rev] = new Edge(G[e.To][e.Rev].To, G[e.To][e.Rev].Cap + d, G[e.To][e.Rev].Rev);; return d; } } } return 0; } public int MaxFlow(int s, int t) { int flow = 0; for (;;) { for (int i = 0; i < Used.Length; i++) { Used[i] = false; } int f = Dfs(s, t, int.MaxValue); #if DEBUG Console.WriteLine("f = "+ f); #endif if (f == 0) return flow; flow += f; } } } */