TopCoder Open 2R 250 - SnowPlow

TCO

問題

N ノードをつなぐ有向グラフが与えられる．2 ノード A, B について A→B と B→A のエッジ数は等しい．0 番ノードからそのグラフを辿った時に全エッジを渡る(ことができる)場合に渡るエッジの最小数はいくつ？

考え方

全エッジが一筆書きできれば最短なのは自明である．後は適当な経路でもって往復すれば（できることがわかれば）いいので，

  1. 0 と接続しているノードの 1 つとを往復する．
  2. 現在のルート中にあるノードから未踏エッジがあったらそのエッジを往復する．
  3. 2に戻る．
  4. ルートから派生する未踏エッジが無くなったら終了．それでも未踏エッジが残っていれば-1．

2の詳細だが，-A-B-C- という接続について →A→B→C→…→C→B→A→ の時に B-D があるとすると，→A→B→D→B→C→…→C→B→A→ にするわけである．

コード

#include <vector>
#include <string>
using namespace std;

class SnowPlow
{
  int n;
  int rec(vector<string>& r, int s)
  {
    int ret = 0;
    for( int d = 0 ; d < n ; ++d ) {
      if( r[s][d] > '0' ) {
        --r[s][d];
        ret += rec(r, d) + 1;
      }
    }
    return ret;
  }
  int allSum(vector<string>& r)
  {
    int ret = 0;
    for( int i = 0 ; i < n ; ++i )
      for( int j = 0 ; j < n ; ++j )
        ret += r[i][j] - '0';
    return ret;
  }
public:
  int solve(vector<string> roads)
  {
    n = roads.size();
    int sum = allSum(roads);
    if( rec(roads, 0) == sum ) return sum;
    return -1;
  }
};