// LLP-WeightedVertexCover: primal-dual 2-approximation for weighted vertex cover.
// Edges are indexed by pairs; G[e] is the price on edge e.
// forbidden: edge {u,v} is slack (neither endpoint tight).
// advance: raise G[e] by the uniform step r.

class LLPWeightedVertexCover {
  void LLPWeightedVertexCover(int[][] adj, double[] w) {
    int nv = w.length;
    double[][] G = new double[nv][nv];
    boolean changed = true;
    while (changed) {
      changed = false;
      double r = computeStep(adj, w, G, nv);
      if (r <= 0.0) { changed = false; };
      int u = 0;
      while (u < nv) {
        int v = u + 1;
        while (v < nv) {
          if (adj[u][v] == 1 && !tight(u, adj, w, G, nv) && !tight(v, adj, w, G, nv)) {
            G[u][v] = G[u][v] + r;
            G[v][u] = G[v][u] + r;
            changed = true;
          };
          v = v + 1;
        };
        u = u + 1;
      }
    };
  }

  boolean tight(int v, int[][] adj, double[] w, double[][] G, int nv) {
    double sum = 0.0;
    int u = 0;
    while (u < nv) {
      if (adj[u][v] == 1) { sum = sum + G[u][v]; };
      u = u + 1;
    };
    return sum >= w[v];
  }

  double computeStep(int[][] adj, double[] w, double[][] G, int nv) {
    double r = infinity;
    int v = 0;
    while (v < nv) {
      int slackDeg = 0;
      int u = 0;
      while (u < nv) {
        if (adj[u][v] == 1 && !tight(u, adj, w, G, nv) && !tight(v, adj, w, G, nv)) {
          slackDeg = slackDeg + 1;
        };
        u = u + 1;
      };
      if (slackDeg > 0) {
        double sum = 0.0;
        u = 0;
        while (u < nv) {
          if (adj[u][v] == 1) { sum = sum + G[u][v]; };
          u = u + 1;
        };
        double ratio = (w[v] - sum) / slackDeg;
        if (ratio < r) { r = ratio; };
      };
      v = v + 1;
    };
    return r;
  }
}