結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | syoken_desuka |
提出日時 | 2015-05-04 21:48:33 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 21,101 bytes |
コンパイル時間 | 3,070 ms |
コンパイル使用メモリ | 114,852 KB |
実行使用メモリ | 27,388 KB |
最終ジャッジ日時 | 2024-07-05 19:00:26 |
合計ジャッジ時間 | 2,207 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
27,248 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | AC | 29 ms
25,080 KB |
testcase_04 | WA | - |
testcase_05 | AC | 30 ms
24,948 KB |
testcase_06 | AC | 30 ms
27,252 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 31 ms
25,172 KB |
testcase_10 | AC | 32 ms
25,096 KB |
testcase_11 | AC | 31 ms
27,080 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 28 ms
25,172 KB |
testcase_15 | WA | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
#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 } } /// <summary> /// 標準入力読み取り支援,自作(某最速の人を参考) /// </summary> #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(); ///0 s 1 t 2 2+n kantoku 2+n+1 2+n+m esi List<grl.Edge>[] G = new List<grl.Edge>[2+n+m]; for (int i = 0; i < 2 + n + m ; i++) { G[i] = new List<grl.Edge>(); } for (int i = 0; i < jjj.Length; i++) { grl.AddEdge(ref G,0,2+i,jjj[i]); } for (int i = 0; i < c.Length; i++) { grl.AddEdge(ref G, 2 + n + i, 1, c[i]); } 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, 2 + j, 2 + n + i, jjj[j]); } } Console.WriteLine( grl.MaxFlow(G,2+n+m,0,1) - w >= 0 ? "SHIROBAKO":"BANSAKUTUKITA"); #if DEBUG Console.WriteLine("t");//local check #endif } } public static class GraphLibrary { public struct Edge { /// <summary> /// 最大流の場合は逆辺 rev /// </summary> public int Rev; public int To; /// <summary> /// 最大流の場合は容量 /// </summary> 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<Edge>[] G; /// <summary> /// 頂点のインデックスは 0 ~ v-1; /// </summary> /// <param name="v">頂点数</param> public Graph(int v) { G = new List<Edge>[v]; for (int i = 0; i < G.Length; i++) { G[i] = new List<Edge>(); } } public void AddEdge(Edge edge) { G[edge.Rev].Add(edge); } } #region UTILITY static bool IsInfinity(int a) { return a == int.MaxValue; } #endregion UTILITY /// <summary> /// 最短経路長を求める /// </summary> /// <param name="v">点の数</param> /// <param name="s">始点 0 ~ v-1</param> /// <param name="ed">辺の情報</param> /// <returns>d[i]: sからiへの最短経路長</returns> 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; } /// <summary> /// 負の閉路が存在するかどうか /// </summary> /// <param name="v">頂点の数</param> /// <param name="ed">辺の集合</param> /// <returns>負の閉路が存在するかどうか</returns> 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; } /// <summary> /// 負の閉路がある場合、無視できるかどうか /// </summary> /// <param name="v"></param> /// <param name="s"></param> /// <param name="ed"></param> /// <returns></returns> public static bool DoesHaveNegativeLoop(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<int> canReachNodesFromS = new HashSet<int>(); 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); } /// <summary> /// 最短経路長を求める /// </summary> /// <param name="graph">二次元マップ</param> /// <returns>d[i][j]]: iからjへの最短経路長</returns> 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; } /// <summary> /// 連結なグラフの最小全域木を求める /// </summary> /// <param name="v">頂点の数</param> /// <param name="ed">辺の集合 to, from は気にしなくてよい</param> /// <returns>最小全域木の重み</returns> 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<Edge>[] 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<Edge>[] G, int v , int s, int t) { MaxFlowSolver solver = new MaxFlowSolver(); return solver.MaxFlow(G, v, s, t); } private class MaxFlowSolver { private List<Edge>[] G; private int[] Level; private int[] Iter; public MaxFlowSolver() { } void BFSForLevelSetting(int s) { Queue<int> que = new Queue<int>(); 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<Edge>[] G, int v,int s, int t) { this.G = (List<Edge>[])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 /// <summary> /// ダイクストラ法に使うつもりの優先度付きキュー /// インナークラス /// </summary> private class PriorityQueueForGL { int[] array; int count = 0; Comparison<int> comparison; // <param name="comparison">intに対する比較方向を示すデリゲート, (a,b)のとき返り値intに a_int - b_int (a > b) なら昇順,逆なら降順</param> public void SetOptionData(Comparison<int> comparison, int MaxCount) { this.comparison = comparison; array = new int[MaxCount]; count = 0; } /// <summary> /// ヒープ化されている配列リストに新しい要素を追加する。 /// </summary> /// <param name="array">対象の配列リスト</param> 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; } } /// <summary> /// ヒープから指定した値を削除する。 /// </summary> /// <param name="array">対象の配列リスト</param> 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; } /// <summary> /// 要素のプッシュ. /// </summary> /// <param name="elem">挿入したい要素</param> public void Push(int elem) { PushHeap(elem); } /// <summary> /// 要素をポップ.出したデータはコレクションの中から消える /// </summary> /// <returns></returns> public int Pop() { return PopHeap(); } /// <summary> /// 要素を全て消去する /// </summary> public void Clear() { for (int i = 0; i < array.Length; i++) array[i] = 0; } } /// <summary> /// UF木、蟻本より /// </summary> class UnionFindTree { int[] Par; int[] Rank; /// <summary> /// nの要素数を管理するUF木 /// </summary> /// <param name="n"></param> public UnionFindTree(int n) { this.Par = new int[n]; this.Rank = new int[n]; for (int i = 0; i < n; i++) { Par[i] = i; } } /// <summary> /// 木の根を求める /// </summary> /// <param name="x"></param> /// <returns></returns> private int Find(int x) { if (Par[x] == x) return x; else { Par[x] = Find(Par[x]); return Par[x]; } } /// <summary> /// xとyの属する集合を併合 /// </summary> /// <param name="x"></param> /// <param name="y"></param> 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]++; } } /// <summary> /// xとyが同じ集合に属するか否か /// </summary> /// <param name="x"></param> /// <param name="y"></param> /// <returns></returns> 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; } } /// <summary> /// 二次元グリッドなどの文字列で与えられたマップなどで、 /// 手軽にデータ変換を適用するためのクラス /// </summary> public static class CharInterpreter { /// <summary> /// 変換用辞書 /// </summary> private static Dictionary<char, int> MapToInt = new Dictionary<char, int>(); /// <summary> /// 変換法則を追加する /// </summary> /// <param name="c">char文字</param> /// <param name="i">対応する整数値</param> public static void AddCorrespondence(char c,int i) { MapToInt.Add(c,i); } /// <summary> /// 文字列に対して、対応付けされた /// 例外処理をしていないので注意 /// </summary> /// <returns>対応対応がなかった場合はバグる;;</returns> public static int Inquiry(char c) { int ret = 0; MapToInt.TryGetValue(c, out ret); return ret; } /// <summary> /// 指定された変換法則の元でint[,]の二次元平面を生成する /// 対応関係がない場合の例外処理をしていないので注意 /// </summary> /// <param name="field">配列の各文字列の長さが全て同じでないとうまく作動しないので注意</param> /// <returns> int[ field.length , field[0].length]型の配列 </returns> 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<Edge>[] G, int v , int s, int t) { MaxFlowSolver solver = new MaxFlowSolver(G, v); return solver.MaxFlow(s, t); } private class MaxFlowSolver { private List<Edge>[] G; private bool[] Used; public MaxFlowSolver(List<Edge>[] 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; } } } */