結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
 Grenache
|
| 提出日時 | 2016-09-11 20:16:52 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 139 ms / 2,000 ms |
| コード長 | 7,345 bytes |
| コンパイル時間 | 3,907 ms |
| コンパイル使用メモリ | 85,144 KB |
| 実行使用メモリ | 55,600 KB |
| 最終ジャッジ日時 | 2024-09-23 07:08:49 |
| 合計ジャッジ時間 | 10,905 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 65 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder421 {private static Scanner sc;private static Printer pr;private static void solve() {int n = sc.nextInt();int m = sc.nextInt();int white = 0;int black = 0;char[][] s = new char[n][];for (int i = 0; i < n; i++) {s[i] = sc.next().toCharArray();for (char c : s[i]) {if (c == 'w') {white++;} else if (c == 'b') {black++;}}}Dinic di = new Dinic(n * m + 2);int source = n * m;int sink = source + 1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (s[i][j] == 'w') {di.addEdge(source, i * m + j, 1);if (i > 0 && s[i - 1][j] == 'b') {di.addEdge(i * m + j, (i - 1) * m + j, 1);}if (i < n - 1 && s[i + 1][j] == 'b') {di.addEdge(i * m + j, (i + 1) * m + j, 1);}if (j > 0 && s[i][j - 1] == 'b') {di.addEdge(i * m + j, i * m + j - 1, 1);}if (j < m - 1 && s[i][j + 1] == 'b') {di.addEdge(i * m + j, i * m + j + 1, 1);}} else if (s[i][j] == 'b') {di.addEdge(i * m + j, sink, 1);}}}int p1 = Math.abs(white - black);int p3 = di.getMaxflow(source, sink);int p2 = Math.max(white, black) - p1 - p3;pr.println(p3 * 100 + p2 * 10 + p1);}private static class Dinic {private static final int INF = Integer.MAX_VALUE;ArrayList<Edge>[] edges;int n;@SuppressWarnings("unchecked")Dinic(int n) {this.n = n;edges = new ArrayList[n];for (int ii = 0; ii < n; ii++) {edges[ii] = new ArrayList<Edge>();}checkedTo = new int[this.n];level = new int[this.n];}// i, j:0-indexedpublic void addEdge(int i, int j, int c) {edges[i].add(new Edge(j, c, edges[j].size(), false));// add reverse edgeedges[j].add(new Edge(i, c, edges[i].size() - 1, true));}public int getMaxflow(int s, int t) {// initialize flowfor (int i = 0; i < edges.length; i++) {for (Edge e : edges[i]) {if (!e.revFlag) {e.f = 0;} else {e.f = e.w;}}}int ret = 0;while (true) {Arrays.fill(level, -1);bfs(s);if (level[t] == -1) {break;}Arrays.fill(checkedTo, 0);int augmentation;while ((augmentation = dfs(s, t, INF)) > 0) {ret += augmentation;}}return ret;}private static int[] checkedTo;private static int[] level;// no capacity edges must be removedprivate void bfs(int s) {Queue<Integer> q = new ArrayDeque<Integer>();level[s] = 0;q.add(s);while (!q.isEmpty()) {int u = q.remove();for (Edge e : edges[u]) {if (level[e.v] == -1 && e.w - e.f > 0) {level[e.v] = level[u] + 1;q.add(e.v);}}}}// find max flow (less than f), on u -> v path// next vertex must has larger levelprivate int dfs(int u, int v, int f) {if (u == v) {return f;}for (; checkedTo[u] < edges[u].size(); checkedTo[u]++) {Edge e = edges[u].get(checkedTo[u]);if (level[e.v] > level[u] && e.w - e.f > 0) {int a = dfs(e.v, v, Math.min(f, e.w - e.f));if (a != 0) {e.f += a;edges[e.v].get(e.revIndex).f -= a;return a;}}}return 0;}private static class Edge {// int u; // fromint v; // toint w; // costint f; // flowint revIndex; // index of reverse edgeboolean revFlag; // flag of reverse edgeEdge(int v, int w, int re, boolean f) {// this.u = u;this.v = v;this.w = w;this.f = 0;this.revIndex = re;this.revFlag = f;}}}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}private boolean isPrintable(int ch) {return ch >= '!' && ch <= '~';}private boolean isCRLF(int ch) {return ch == '\n' || ch == '\r' || ch == -1;}private int nextPrintable() {try {int ch;while (!isPrintable(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}return ch;} catch (IOException e) {throw new NoSuchElementException();}}String next() {try {int ch = nextPrintable();StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (isPrintable(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int nextInt() {try {// parseInt from Integer.parseInt()boolean negative = false;int res = 0;int limit = -Integer.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Integer.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}int multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}long nextLong() {try {// parseLong from Long.parseLong()boolean negative = false;long res = 0;long limit = -Long.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Long.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}long multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}float nextFloat() {return Float.parseFloat(next());}double nextDouble() {return Double.parseDouble(next());}String nextLine() {try {int ch;while (isCRLF(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (!isCRLF(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}void close() {try {br.close();} catch (IOException e) {// throw new NoSuchElementException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}