cafelier@SRM

SRM435 1000

あとで | 21:44 |

惜しいところまでは行ってたようだ。

// 2部グラフの最大マッチ ----------------------------
typedef int           vert;
typedef vert          edge;
typedef vector<edge>  edges;
typedef vector<edges> graph;

bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
{
  for(int i=0; i<G[v].size(); ++i) {
    vert u = G[v][i];
    if( visited[u] ) continue;
    visited[u] = true;

    if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
      { matchTo[v]=u, matchTo[u]=v; return true; }
  }
  return false;
}

template<int NV>
int biMatch( graph& G, int L )
{
  vector<vert> matchTo(G.size(), -1);
  int ans = 0;
  for(vert v=0; v<L; ++v) {
    bool visited[NV] = {};
    if( augment(G, v, matchTo, visited) )
      ++ans;
  }
  return ans;
}

// 本体 -------------------------------------------
class CompanyRestructuring {
public:
  int fewestDivisions(vector <string> hasManaged) 
  {
    int N = hasManaged.size();

    bool hm[50][50], hmStar[50][50];
    for(int i=0; i<N; ++i)
      for(int j=0; j<N; ++j)
        hm[i][j] = hmStar[i][j] = hasManaged[i][j]=='Y';

    for(int k=0; k<N; ++k)
      for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
          hmStar[i][j] |= hmStar[i][k] & hmStar[k][j];

    graph g(N);
    int nextID = N;
    for(int p=0; p<N; ++p)
    {
      vector<int> cs;
      vector<int> pi;

      for(int c=0; c<N; ++c)
        if( hm[p][c] && !hmStar[c][p] )
        {
          int pid = -1;
          
          for(int j=0; j<cs.size(); ++j)
            if( hmStar[c][cs[j]] && hmStar[cs[j]][c] )
              {pid = pi[j]; break;}

          if(pid<0) pid = nextID++;
          cs.push_back(c);
          pi.push_back(pid);
          g[c].push_back(pid);
        }
    }
    g.resize(nextID);

    return N - biMatch<50*50*2>(g, N);
  }
};

辺を１個つかうごとに連結成分の個数は１個減るので、「連結成分の個数」って評価関数は単純に「使う辺が多ければ多いほどよい」に他ならない。

まずは「兄弟間に（元のグラフでの）ループがあってはいけない」という条件を無視して考えると、

• 左側にN点、右側にN*N点のグラフを作って最大マッチ
  • 左の x 番目と右の N*y+x 番目を結ぶことと、x の親を y とすることが対応する
  • 親は1つ（ルートなら0個）という条件は、マッチングなので左のxから出る辺を2本同時に選んだりしないことで表現
  • グラフを作るときに、「親からは子へは（元のグラフでの）パスがある」「子から親への（元のグラフでの）パスがあってはいけない」という条件を満たす辺だけをあらかじめ入れておく。これを満たしていればツリーがDAGしか作らないのでその辺の制約もOK

という作り方。「兄弟間に（元のグラフでの）ループがあってはいけない」という条件は、この関係が同値関係なことを考えると、親を表す右のノードを N*y+x と全部別々にするんじゃなくて、兄弟になれないxどうしは同じ親ノードを指すようにグラフを作る。これでマッチングという条件から親を共有しないという条件が加味される。