제출 #1148118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148118		rebe__1	Coin Collecting (JOI19_ho_t4)	Java	37 / 100	1092 ms	249816 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {

  static class Edge {
    int to, rev, cap, cost;
    public Edge(int to, int rev, int cap, int cost) {
      this.to = to;
      this.rev = rev;
      this.cap = cap;
      this.cost = cost;
    }
  }

  static final int INF = 1000000000;

  ArrayList<Edge>[] graph;
  int N;

  public joi2019_ho_t4(int N) {
    this.N = N;
    graph = new ArrayList[N];
    for (int i = 0; i < N; i++) {
      graph[i] = new ArrayList<>();
    }
  }

  void addEdge(int s, int t, int cap, int cost) {
    graph[s].add(new Edge(t, graph[t].size(), cap, cost));
    graph[t].add(new Edge(s, graph[s].size() - 1, 0, -cost));
  }

  int minCostFlow(int s, int t, int f) {
    int res = 0;
    int[] dist = new int[N];
    int[] prevV = new int[N];
    int[] prevE = new int[N];

    while (f > 0) {
      Arrays.fill(dist, INF);
      dist[s] = 0;
      boolean[] inQueue = new boolean[N];
      Queue<Integer> que = new LinkedList<>();
      que.add(s);
      inQueue[s] = true;
      while (!que.isEmpty()) {
        int u = que.poll();
        inQueue[u] = false;
        for (int i = 0; i < graph[u].size(); i++) {
          Edge e = graph[u].get(i);
          if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
            dist[e.to] = dist[u] + e.cost;
            prevV[e.to] = u;
            prevE[e.to] = i;
            if (!inQueue[e.to]) {
              que.add(e.to);
              inQueue[e.to] = true;
            }
          }
        }
      }
      if (dist[t] == INF) {
        return -1;
      }
      int d = f;
      for (int v = t; v != s; v = prevV[v]) {
        d = Math.min(d, graph[prevV[v]].get(prevE[v]).cap);
      }
      f -= d;
      res += d * dist[t];
      for (int v = t; v != s; v = prevV[v]) {
        Edge e = graph[prevV[v]].get(prevE[v]);
        e.cap -= d;
        graph[v].get(e.rev).cap += d;
      }
    }
    return res;
  }

  private static int constrain(int value, int min, int max) {
    if (value < min) return min;
    if (value > max) return max;
    return value;
  }

  private static long calculateMovesToBoundary(int col, int row, int numColumns) {
    long moves = 0;
    if (row < 1) moves += (1 - row);
    if (row > 2) moves += (row - 2);
    if (col < 1) moves += (1 - col);
    if (col > numColumns) moves += (col - numColumns);
    return moves;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int numColumns = sc.nextInt();
    int totalCoins = 2 * numColumns;
    int[][] grid = new int[3][numColumns + 1];
    long boundaryCost = 0;

    for (int i = 0; i < totalCoins; i++) {
      int col = sc.nextInt();
      int row = sc.nextInt();
      boundaryCost += calculateMovesToBoundary(col, row, numColumns);
      int validCol = constrain(col, 1, numColumns);
      int validRow = constrain(row, 1, 2);
      grid[validRow][validCol]++;
    }

    int nodes = 2 * numColumns;
    int[] supply = new int[nodes];
    for (int c = 1; c <= numColumns; c++) {
      for (int r = 1; r <= 2; r++) {
        int idx = (c - 1) * 2 + (r - 1);
        supply[idx] = grid[r][c] - 1;
      }
    }

    int s = nodes;
    int t = nodes + 1;
    int totalNodes = nodes + 2;
    joi2019_ho_t4 mcf = new joi2019_ho_t4(totalNodes);

    for (int c = 1; c < numColumns; c++) {
      for (int r = 1; r <= 2; r++) {
        int u = (c - 1) * 2 + (r - 1);
        int v = (c) * 2 + (r - 1);
        mcf.addEdge(u, v, INF, 1);
        mcf.addEdge(v, u, INF, 1);
      }
    }

    for (int c = 1; c <= numColumns; c++) {
      int u = (c - 1) * 2 + 0;
      int v = (c - 1) * 2 + 1;
      mcf.addEdge(u, v, INF, 1);
      mcf.addEdge(v, u, INF, 1);
    }

    int totalPositive = 0;
    for (int i = 0; i < nodes; i++) {
      if (supply[i] > 0) {
        mcf.addEdge(s, i, supply[i], 0);
        totalPositive += supply[i];
      } else if (supply[i] < 0) {
        mcf.addEdge(i, t, -supply[i], 0);
      }
    }

    int flowCost = mcf.minCostFlow(s, t, totalPositive);

    long answer = boundaryCost + flowCost;
    System.out.println(answer);
  }
}

컴파일 시 표준 에러 (stderr) 메시지

Note: joi2019_ho_t4.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

=======

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 0 / 63