結果
問題 | No.2713 Just Solitaire |
ユーザー | kakel-san |
提出日時 | 2024-04-14 22:34:21 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 6,770 bytes |
コンパイル時間 | 11,685 ms |
コンパイル使用メモリ | 169,580 KB |
実行使用メモリ | 189,140 KB |
最終ジャッジ日時 | 2024-10-04 02:52:44 |
合計ジャッジ時間 | 15,373 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
30,464 KB |
testcase_01 | AC | 62 ms
30,712 KB |
testcase_02 | AC | 62 ms
30,588 KB |
testcase_03 | AC | 62 ms
30,336 KB |
testcase_04 | AC | 63 ms
30,848 KB |
testcase_05 | AC | 62 ms
30,720 KB |
testcase_06 | AC | 67 ms
31,104 KB |
testcase_07 | AC | 63 ms
30,848 KB |
testcase_08 | AC | 63 ms
30,336 KB |
testcase_09 | AC | 63 ms
30,336 KB |
testcase_10 | AC | 63 ms
30,336 KB |
testcase_11 | AC | 63 ms
30,296 KB |
testcase_12 | AC | 62 ms
30,208 KB |
testcase_13 | AC | 65 ms
30,968 KB |
testcase_14 | AC | 67 ms
30,592 KB |
testcase_15 | AC | 63 ms
30,464 KB |
testcase_16 | AC | 63 ms
30,336 KB |
testcase_17 | AC | 64 ms
30,672 KB |
testcase_18 | AC | 63 ms
30,336 KB |
testcase_19 | AC | 68 ms
31,232 KB |
testcase_20 | AC | 61 ms
30,168 KB |
testcase_21 | AC | 63 ms
30,168 KB |
testcase_22 | AC | 62 ms
30,720 KB |
testcase_23 | AC | 64 ms
30,672 KB |
testcase_24 | AC | 71 ms
32,256 KB |
testcase_25 | AC | 74 ms
31,952 KB |
testcase_26 | AC | 70 ms
32,128 KB |
testcase_27 | AC | 71 ms
32,000 KB |
testcase_28 | AC | 68 ms
31,232 KB |
testcase_29 | AC | 71 ms
32,128 KB |
testcase_30 | AC | 71 ms
32,000 KB |
testcase_31 | AC | 70 ms
32,128 KB |
testcase_32 | AC | 71 ms
32,000 KB |
testcase_33 | AC | 72 ms
189,140 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (99 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray(); static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, m) = (c[0], c[1]); var a = NList; var b = NList; var map = NMap(m); var g = new MaxFlowGraph(n + m + 2); var s = n + m; for (var i = 0; i < n; ++i) { g.AddEdge(i, s + 1, a[i]); } for (var i = 0; i < m; ++i) { g.AddEdge(s, n + i, b[i]); for (var j = 1; j < map[i].Length; ++j) { g.AddEdge(n + i, map[i][j], int.MaxValue); } } var ans = - g.Flow(s, s + 1); foreach (var bi in b) ans += bi; WriteLine(ans); } // 最大フローグラフ // MaxFlowGraph(n) n:頂点数 // AddEdge(from, to, cap) from,to:0-indexed cap:最大用量 // Flow(from, to) 最大流量を求める 各辺の流量を変更 // Flow(from, to, flowLimit) // MinCut(from) Flow(最小カット)実行後の残余グラフで各頂点への到達可能性を取得 // GetEdge(i), GetEdges() 内部の辺の状態を取得 // ChangeEdge(i, newCap, newFlow) 対象辺の流量を変更 class MaxFlowGraph { int _n; long max = long.MaxValue; class EdgeI { public int to { get; private set; } public int rev { get; private set; } public long cap { get; set; } public EdgeI(int to, int rev, long cap) { this.to = to; this.rev = rev; this.cap = cap; } } List<KeyValuePair<int, int>> pos = new List<KeyValuePair<int, int>>(); List<EdgeI>[] g; public MaxFlowGraph(int n) { _n = n; g = new List<EdgeI>[n]; for (var i = 0; i < n; ++i) g[i] = new List<EdgeI>(); } public int AddEdge(int from, int to, long cap) { var m = pos.Count; pos.Add(new KeyValuePair<int, int>(from, g[from].Count)); g[from].Add(new EdgeI(to, g[to].Count, cap)); g[to].Add(new EdgeI(from, g[from].Count - 1, 0)); return m; } public class Edge { public int from { get; private set; } public int to { get; private set; } public long cap { get; private set; } public long flow { get; private set; } public Edge(int from, int to, long cap, long flow) { this.from = from; this.to = to; this.cap = cap; this.flow = flow; } } public Edge GetEdge(int i) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; return new Edge(pos[i].Key, e.to, e.cap + re.cap, re.cap); } public List<Edge> GetEdges() { var m = pos.Count; var result = new List<Edge>(); for (var i = 0; i < m; ++i) result.Add(GetEdge(i)); return result; } public void ChangeEdge(int i, long new_cap, long new_flow) { var m = pos.Count; var e = g[pos[i].Key][pos[i].Value]; var re = g[e.to][e.rev]; e.cap = new_cap - new_flow; re.cap = new_flow; } public long Flow(int s, int t) { return Flow(s, t, max); } public long Flow(int s, int t, long limit) { var level = new int[_n]; var iter = new int[_n]; var que = new Queue<int>(); void bfs() { for (var i = 0; i < _n; ++i) level[i] = -1; level[s] = 0; que.Clear(); que.Enqueue(s); while (que.Count > 0) { var v = que.Dequeue(); foreach (var e in g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.Enqueue(e.to); } } } long dfs(int v, long up) { if (v == s) return up; long res = 0; var level_v = level[v]; for (var i = iter[v]; i < g[v].Count; ++i) { var e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; long d = dfs(e.to, Min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) break; } return res; } long flow = 0; while (flow < limit) { bfs(); if (level[t] == -1) break; for (var i = 0; i < iter.Length; ++i) iter[i] = 0; while (flow < limit) { var f = dfs(t, limit - flow); if (f == 0) break; flow += f; } } return flow; } long Min(long a, long b) { return a.CompareTo(b) < 0 ? a : b; } public bool[] MinCut(int s) { var visited = new bool[_n]; var que = new Queue<int>(); que.Enqueue(s); while (que.Count > 0) { var p = que.Dequeue(); visited[p] = true; foreach (var e in g[p]) { if (e.cap != 0 && !visited[e.to]) { visited[e.to] = true; que.Enqueue(e.to); } } } return visited; } } }