TopCoder SRM 693 Div1 Easy: BiconnectedDiv1

解法

最小費用流そのものやんけ！！！！

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class BiconnectedDiv1 {

  public int minimize(int[] w1, int[] w2) {
    int V = w1.length + 1;
    MinimumCostFlow flow = new MinimumCostFlow(V);
    for (int i = 0; i < w1.length; i++) flow.addEdge(i, i + 1, 1, w1[i]);
    for (int i = 0; i < w2.length; i++) flow.addEdge(i, i + 2, 1, w2[i]);
    return flow.run(0, V - 1, 2);
  }

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

    private static final int INF = (int) 1e9;
    private ArrayList<ArrayList<Edge>> G;
    private int V;
    int[] potential;
    int[] dist;
    int[] prevV, prevE;

    MinimumCostFlow(int V) {
      this.V = V;
      G = new ArrayList<>(V);
      for (int i = 0; i < V; i++) G.add(new ArrayList<>());
      potential = new int[V];
      dist = new int[V];
      prevE = new int[V];
      prevV = new int[V];
    }

    void addEdge(int from, int to, int cap, int cost) {
      G.get(from).add(new Edge(to, cap, cost, G.get(to).size()));
      G.get(to).add(new Edge(from, 0, -cost, G.get(from).size() - 1));
    }

    int run(int s, int t, int flow) {
      int cost = 0;
      Arrays.fill(potential, 0);
      while (flow > 0) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
          @Override
          public int compare(int[] o1, int[] o2) {
            return Integer.compare(o1[0], o2[0]);
          }
        });
        Arrays.fill(dist, INF);
        dist[s] = 0;
        queue.add(new int[]{0, s});
        while (!queue.isEmpty()) {
          int[] p = queue.poll();
          int v = p[1];
          if (dist[v] < p[0]) continue;
          for (int i = 0; i < G.get(v).size(); i++) {
            Edge e = G.get(v).get(i);
            int u = e.to;
            if (e.cap > 0 && dist[u] > dist[v] + e.cost + potential[v] - potential[u]) {
              dist[u] = dist[v] + e.cost + potential[v] - potential[u];
              prevV[u] = v;
              prevE[u] = i;
              queue.add(new int[]{dist[u], u});
            }
          }
        }
        if (dist[t] == INF) {
          return -1;
        }
        for (int v = 0; v < V; v++) potential[v] += dist[v];

        int d = flow;
        for (int v = t; v != s; v = prevV[v]) d = Math.min(d, G.get(prevV[v]).get(prevE[v]).cap);
        flow -= d;
        cost += d * potential[t];
        for (int v = t; v != s; v = prevV[v]) {
          Edge e = G.get(prevV[v]).get(prevE[v]);
          e.cap -= d;
          G.get(v).get(e.rev).cap += d;
        }
      }
      return cost;
    }
  }
}