Submission #183242

---

Source Code Expand

var fs = require('fs')
  , _
;

(function() {
  var ls = fs.readFileSync('/dev/stdin', 'utf8').split('\n').slice(0, -1);
  GLOBAL.readline = function() {
    if (ls.length === 0) return false;
    _ = ls.shift();
    return _;
  };
  GLOBAL.readints = function() {
    if (ls.length === 0) return false;
    _ = words(ls.shift()).map(int);
    return _;
  }
}());

log = console.log;
warn = console.warn;
int = function(x) { return x|0 };
float = function(x) { return +x };

// string ->
function words(x) { return x.split(' ') };
function ints(x) { return words(x).map(int) };

// -> number
function add(x,y) { return x+y };
function max(x,y) { return x>y ? x : y };
function min(x,y) { return x<y ? x : y };

// -> [number]
function sort(ls) { return ls.sort(function(x,y) { return x - y }) };
function iota(n,b,s) {
  b = b||0;
  s = s===void 0?1:s;
  var ret = [];
  for (var i=0;i<n;++i) { ret[i] = b + i * s; }
  return ret;
};

var konst = {
  directed: 'directed',
  undirected: 'undirected',
}

function Graph(N) {
  this.type = konst.undirected;
  this.N = N || 0;
  this.E = {};
}

/// BASIC

// add edge !
Graph.prototype.add = function(u, v, capacity) {
  capacity = capacity || 1;
  var that = this;
  a(u,v);
  if (this.type === konst.undirected) {
    a(v,u);
  }
  function a(u,v) {
    if (!(u in that.E)) that.E[u] = {};
    if (!(v in that.E[u])) that.E[u][v] = 0;
    that.E[u][v] += capacity;
  }
};

// predicate whether has edge (u,v) or not
Graph.prototype.has = function(u, v) {
  return u in this.E && v in this.E[u] && this.E[u][v] > 0 };

// make complete graph
konst.complete = function (N) {
  var g = new Graph(N);
  for (var i=0; i<N-1; ++i) {
    for (var j=i+1; j<N; ++j) {
      g.add(i,j) }}
  return g;
};

/// ALGORITHMS

Graph.prototype.scc = scc;
Graph.prototype.maxflow = maxflow;

function scc() {
  var that = this
    , N = that.N
    , rev = graphReverse(that)
    , vs = []
    , used = []
    , cmp = []
  ;

  function graphReverse(g) {
    var r = {};
    r.E = {};
    for (var u in g.E) {
      for (var v in g.E[u]) {
        if (! (v in r.E)) r.E[v] = {};
        r.E[v][u] = g.E[u][v]
      }
    }
    return r;
  }
  function zeroset() {
    for (var i=0;i<N;++i) used[i] = false;
  }

  function dfs(v) {
    used[v] = true;
    for (var u in that.E[v]) {
      if (!used[u]) dfs(u);
    }
    vs.push(v);
  }

  function rdfs(v, k) {
    used[v] = true;
    cmp[v] = k;
    for (var u in rev.E[v]) {
      if (!used[u]) rdfs(u, k);
    }
  }


  zeroset();
  for (var v=0; v < N; ++v) {
    if (!used[v]) {
      dfs(v); }}
  zeroset();
  var k = 0;
  vs.reverse()
    .forEach(function(v) { if (!used[v]) rdfs(v, k++); })
    ;

  return cmp;

}

function maxflow(s, t) {
  s = s | 0;
  t = t | 0;
  var that = this
    , F  = {}
  ;
  for (var u=0; u<that.N; ++u) {
    F[u] = {};
    for (var v=0; v<that.N; ++v) {
      F[u][v] = 0;
    }
  }

  for (var sum=0, f; f=bfs(); sum += f);
  return sum;

  function bfs() {
    var M = {}    // M[v] is max-flow of `s -> v`
      , P = {}  // parent node of flow path
    ;
    M[s] = 1/0;
    P[s] = false;
    for (var q=[s]; q.length>0; ) {
      var u = q.shift();
      for (var v=0; v<that.N; ++v) {
        if (v in M) continue; // have searched
        var capa = that.has(u,v) ? that.E[u][v] : 0
          , rest = capa - F[u][v] + F[v][u]
        ;
        if (rest <= 0) continue; // cannot flow
        M[v] = Math.min(M[u], rest);
        P[v] = u;
        q.push(v);
        if (v === t) return defer();
      }
    }
    return false;

    function defer() {
      var f = M[t];
      // var path = t;
      for (var v=t;; v=P[v]) {
        var u = P[v];
        // path = u+'->'+path;
        F[u][v] += f;
        if (u === s) break;
      }
      // console.warn(f, path);
      return f;
    }
  }
};


readints();
N = _[0];
G = _[1];
E = _[2];

if (G === 0) {
  log(0);
  process.exit(0);
}

ps = readints();

var g = new Graph(N+1);
g.type = 'undirected';

for (i=0;i<E;++i) {
  readints();
  a = _[0];
  b = _[1];
  g.add(a,b);
}

ps.forEach(function(p) {
  g.add(p, N);
});

log(g.maxflow(0, N))

Submission Info

Judge Result