글 읽기 - 네트워크 플로우 문제인데 소스좀 봐주십시요ㅜ,.ㅜ

kgc0517 6년 전 0

1*2, 2*1 의 형태로 인접한 정점을 고르고 1를 빼주는 문제 입니다.

격자 형태로 각각 소스와 싱크로 해당 정점의 용량만큼 연결해준 상태에서 네트워크 플로우 형식으로 다 돌린 후

남아 있는 값을 더해 총 연산 횟수를 구했습니다.

하도하도 틀려서 다른 분들의 코드를 참조도 해봤는데 어느 부분이 잘못된 건지 제 머리로는 모르겠습니다. ㅜㅜ

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin','utf8').split('\n');
var idx = 0;
var test = parseInt(input[idx++]);
var dx = [1,0,-1,0];
var dy = [0,1,0,-1];
while (test--) {
  var tmp = input[idx++].split(' ').map(function(a){return parseInt(a);});
  var N = tmp[0];
  var M = tmp[1];
  var max = N * M + 2;
  var adj = [];
  var c = [];
  var s = max - 2;
  var e = max - 1;
  var data = [];
  var total = 0;
  for(var i = 0; i < N; i++){
    data[i] = input[idx++].split(' ').map(function(a){return parseInt(a);});
  }

  for(var i = 0; i < max; i++){
    adj[i] = [];
    c[i] = [];
  }
    //격자로 싱크와 소스에 연결과 각 노드 연결.
  for(var i = 0; i < N; i++){
    for(var j = 0; j < M; j++){
      total += data[i][j];
      var curr = i*M+j;
      if (i % 2 === j % 2) {
        adj[s].push(curr);
        adj[curr].push(s);
        c[s][curr] = data[i][j];

        for(var k = 0; k < 4; k++){
          var ny = dy[k] + i;
          var nx = dx[k] + j;
          if(ny < 0 || nx < 0 || nx >= M || ny >= N) continue;
          var next = ny*M+nx;
          adj[curr].push(next);
          adj[next].push(curr);
          c[curr][next] = Infinity;
        }
      }else{
        adj[curr].push(e);
        adj[e].push(curr);
        c[curr][e] = data[i][j];
      }
    }
  }

  var ans = 0;
  while (1) {
    var prev = [];
    for(var i = 0; i < max; i++){
      prev[i] = -1;
    }
    var q = [s];
    while (q.length) {
      var curr = q.shift();
      var len = adj[curr].length;
      for(var i = 0; i < len; i++){
        var next = adj[curr][i];
        if(prev[next] === -1 && c[curr][next] > 0){
          prev[next] = curr;
          q.push(next);
          if(next === e) break;
        }c
      }
    }
    if(prev[e] === -1) break;
    var flow = Infinity;
    for(var i = e; i !== s; i = prev[i]){
      flow = Math.min(flow, c[prev[i]][i]);
    }
    for(var i = e; i !== s; i = prev[i]){
      c[prev[i]][i] -= flow;
      c[i][prev[i]] += flow;
    }
    ans += flow;
  }
  console.log(total - ans);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

네트워크 플로우 문제인데 소스좀 봐주십시요ㅜ,.ㅜ

kgc0517 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말