結果
問題 | No.1479 Matrix Eraser |
ユーザー | 小野寺健 |
提出日時 | 2021-04-29 10:15:46 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 2,480 ms / 3,000 ms |
コード長 | 2,755 bytes |
コンパイル時間 | 4,611 ms |
コンパイル使用メモリ | 75,528 KB |
実行使用メモリ | 268,688 KB |
最終ジャッジ日時 | 2023-09-22 18:11:33 |
合計ジャッジ時間 | 60,298 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 122 ms
55,684 KB |
testcase_01 | AC | 128 ms
55,488 KB |
testcase_02 | AC | 136 ms
56,004 KB |
testcase_03 | AC | 134 ms
56,172 KB |
testcase_04 | AC | 134 ms
56,044 KB |
testcase_05 | AC | 133 ms
55,484 KB |
testcase_06 | AC | 135 ms
55,728 KB |
testcase_07 | AC | 553 ms
80,108 KB |
testcase_08 | AC | 788 ms
96,208 KB |
testcase_09 | AC | 1,267 ms
136,848 KB |
testcase_10 | AC | 2,147 ms
200,732 KB |
testcase_11 | AC | 1,553 ms
159,544 KB |
testcase_12 | AC | 682 ms
88,012 KB |
testcase_13 | AC | 760 ms
96,732 KB |
testcase_14 | AC | 697 ms
90,192 KB |
testcase_15 | AC | 311 ms
64,580 KB |
testcase_16 | AC | 734 ms
92,492 KB |
testcase_17 | AC | 2,397 ms
242,028 KB |
testcase_18 | AC | 2,382 ms
241,684 KB |
testcase_19 | AC | 2,384 ms
241,256 KB |
testcase_20 | AC | 2,480 ms
241,692 KB |
testcase_21 | AC | 2,342 ms
243,036 KB |
testcase_22 | AC | 2,466 ms
242,828 KB |
testcase_23 | AC | 2,327 ms
242,564 KB |
testcase_24 | AC | 2,366 ms
241,388 KB |
testcase_25 | AC | 2,397 ms
242,012 KB |
testcase_26 | AC | 2,387 ms
242,236 KB |
testcase_27 | AC | 1,455 ms
95,784 KB |
testcase_28 | AC | 1,463 ms
94,764 KB |
testcase_29 | AC | 1,537 ms
94,972 KB |
testcase_30 | AC | 1,490 ms
94,620 KB |
testcase_31 | AC | 1,501 ms
92,672 KB |
testcase_32 | AC | 1,164 ms
97,204 KB |
testcase_33 | AC | 1,173 ms
100,212 KB |
testcase_34 | AC | 1,195 ms
94,948 KB |
testcase_35 | AC | 1,227 ms
91,976 KB |
testcase_36 | AC | 1,174 ms
97,584 KB |
testcase_37 | AC | 646 ms
66,692 KB |
testcase_38 | AC | 1,686 ms
132,748 KB |
testcase_39 | AC | 2,045 ms
268,688 KB |
testcase_40 | AC | 213 ms
55,568 KB |
ソースコード
package yukicoder; import java.util.Scanner; import java.util.List; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; public class No1479_2 { private static class Values { public HashMap<Integer, Integer> di, dj; public List<Integer[]> ij; public Values() { di = new HashMap<Integer, Integer> (); dj = new HashMap<Integer, Integer> (); ij = new ArrayList<Integer[]>(); } } private static int V; private static int[] match; private static boolean[] used; private static List<List<Integer>> G; private static void add_edge(int u, int v) { G.get(u).add(v); G.get(v).add(u); } private static boolean dfs(int v) { used[v] = true; for (int u : G.get(v)) { int w = match[u]; if (w < 0 || !used[w] && dfs(w)) { match[v] = u; match[u] = v; return true; } } return false; } private static int bipartite_matching() { int res = 0; match = new int[V]; Arrays.fill(match, -1); for (int v=0; v < V; v++) { if (match[v] < 0) { used = new boolean[V]; if (dfs(v)) { res++; } } } return res; } private static int mpc(int h, int w) { int res = bipartite_matching(); List<Integer> matched = new ArrayList<Integer>(); for (int i=h; i < h+w; i++) { matched.add(match[i]); } int left = h, right = 0; for (int v = 0; v < h; v++) { if (!matched.contains(v)) { left--; for (int u : G.get(v)) { right++; if (match[u] >= 0) { left--; } } } } return left + right; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int H = scan.nextInt(); int W = scan.nextInt(); HashMap<Integer, Values> S = new HashMap<Integer, Values>(); for (int i=0; i < H; i++) { for (int j=0; j < W; j++) { int a = scan.nextInt(); if (a > 0) { if (!S.containsKey(a)) { Values v = new Values(); v.di.put(i, 0); v.dj.put(j, 0); v.ij.add(new Integer[] {0, 0}); S.put(a, v); } else { Values v = S.get(a); int ai, aj; if (v.di.containsKey(i)) { ai = v.di.get(i); } else { ai = v.di.size(); v.di.put(i, ai); } if (v.dj.containsKey(j)) { aj = v.dj.get(j); } else { aj = v.dj.size(); v.dj.put(j, aj); } v.ij.add(new Integer[] {ai, aj}); } } } } scan.close(); int cnt = 0; for (Values v : S.values()) { int h = v.di.size(); int w = v.dj.size(); V = h + w; G = new ArrayList<List<Integer>>(); for (int i=0; i < V; i++) { G.add(new ArrayList<Integer>()); } for (Integer[] i : v.ij) { add_edge(i[0], i[1]+h); } int n = mpc(h, w); cnt += n; } System.out.println(cnt); } }