結果
問題 | No.1479 Matrix Eraser |
ユーザー | 小野寺健 |
提出日時 | 2021-04-29 10:23:02 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 2,397 ms / 3,000 ms |
コード長 | 2,772 bytes |
コンパイル時間 | 3,837 ms |
コンパイル使用メモリ | 75,620 KB |
実行使用メモリ | 260,948 KB |
最終ジャッジ日時 | 2023-09-22 18:18:45 |
合計ジャッジ時間 | 56,184 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 123 ms
55,692 KB |
testcase_01 | AC | 127 ms
55,900 KB |
testcase_02 | AC | 132 ms
55,564 KB |
testcase_03 | AC | 132 ms
55,680 KB |
testcase_04 | AC | 133 ms
55,408 KB |
testcase_05 | AC | 132 ms
55,412 KB |
testcase_06 | AC | 133 ms
55,720 KB |
testcase_07 | AC | 547 ms
79,832 KB |
testcase_08 | AC | 793 ms
96,264 KB |
testcase_09 | AC | 1,218 ms
136,660 KB |
testcase_10 | AC | 2,136 ms
200,460 KB |
testcase_11 | AC | 1,613 ms
168,600 KB |
testcase_12 | AC | 662 ms
87,976 KB |
testcase_13 | AC | 743 ms
97,256 KB |
testcase_14 | AC | 669 ms
90,304 KB |
testcase_15 | AC | 303 ms
64,680 KB |
testcase_16 | AC | 700 ms
92,860 KB |
testcase_17 | AC | 2,259 ms
233,664 KB |
testcase_18 | AC | 2,341 ms
241,128 KB |
testcase_19 | AC | 2,282 ms
234,120 KB |
testcase_20 | AC | 2,239 ms
234,080 KB |
testcase_21 | AC | 2,224 ms
234,996 KB |
testcase_22 | AC | 2,397 ms
235,460 KB |
testcase_23 | AC | 2,228 ms
233,968 KB |
testcase_24 | AC | 2,282 ms
235,884 KB |
testcase_25 | AC | 2,270 ms
235,296 KB |
testcase_26 | AC | 2,244 ms
235,304 KB |
testcase_27 | AC | 1,375 ms
93,428 KB |
testcase_28 | AC | 1,426 ms
94,632 KB |
testcase_29 | AC | 1,374 ms
94,680 KB |
testcase_30 | AC | 1,400 ms
94,056 KB |
testcase_31 | AC | 1,375 ms
94,656 KB |
testcase_32 | AC | 1,116 ms
95,300 KB |
testcase_33 | AC | 1,150 ms
95,672 KB |
testcase_34 | AC | 1,190 ms
91,540 KB |
testcase_35 | AC | 1,160 ms
92,400 KB |
testcase_36 | AC | 1,233 ms
98,852 KB |
testcase_37 | AC | 638 ms
64,328 KB |
testcase_38 | AC | 1,525 ms
140,452 KB |
testcase_39 | AC | 1,980 ms
260,948 KB |
testcase_40 | AC | 120 ms
55,796 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(); boolean[] matched = new boolean[h]; for (int i=h; i < h+w; i++) { int v = match[i]; if (v >= 0) { matched[v] = true; } } int left = h, right = 0; for (int v = 0; v < h; v++) { if (!matched[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); } }