cafelier@SRM

Facebook Hacker Cup 2012 R2 Road Removal

FHC, あとで | 21:49 |

今回はUnionFind祭りだった。

• 長いので重要な都市を「黒」と重要でない都市を「白」とする。

struct UnionFind
{
   vector<int> uf, sz;
   int nc;

   UnionFind(int N): uf(N), sz(N,1), nc(N)
      { for(int i=0; i<N; ++i) uf[i] = i; }
   int size()
      { return nc; }
   int Find(int a)
      { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
   bool Union(int a, int b)
      {
         a = Find(a);
         b = Find(b);
         if( a != b )
         {
            if( sz[a] >= sz[b] ) swap(a, b);
            uf[a] = b;
            sz[b] += sz[a];
            --nc;
         }
         return (a!=b);
      }
};

typedef int vert;
typedef tuple<vert,vert> edge;

int solve(const vector<edge>& edges, int N, int K)
{
   int removed = 0;

   // とりあえず白白辺を全部結ぶ
   UnionFind uf(N);
   for(edge e : edges) {
      vert a = get<0>(e);
      vert b = get<1>(e);
      if( a >= K && b >= K )
         uf.Union(a,b);
   }

   // 他の辺はサイクル作らないように結ぶ
   for(edge e : edges) {
      vert a = get<0>(e);
      vert b = get<1>(e);
      if( a < K || b < K )
         if( !uf.Union(a,b) )
            ++removed;
   }
   return removed;
}

int main()
{
   int T; cin >> T;
   for(int C=1; C<=T; ++C)
   {
      int N, M, K; cin >> N >> M >> K;
      vector<edge> edges;
      for(int i=0; i<M; ++i) {
         int a,b; cin >> a >> b;
         edges.emplace_back(a, b);
      }
      cout << "Case #" << C << ": " << solve(edges, N, K) << endl;
   }
}

• 仮定１： 白白辺はgreedyに全部結んじゃって良い
  • 白白辺 e を含まない最適解が存在したとする
  • その解に e を足すと（最適性より）黒ノードを含むサイクルができる
  • そのサイクル中の白黒辺を消して代わりに e を入れてもサイクルなしなので(※)これも最適解になる
    • ※: eを足した結果できるサイクルは1つだけ。2つ一気にできたとすると絵を描いてみると元々サイクルがあったことになってしまうことがわかる。
• 仮定２： 白白辺で結んだ同値類を１点とみなして、あとは普通に最小全域森を作るのが最適
  • 森なら新しくサイクル作ってないので条件は満たす。
  • それより枝を多く入れると必ずサイクルができてしまう。もう白白辺は存在しないので、この段階でできてしまったサイクルは必ず黒ノードを含むから失格。
  • 故に最小全域森が最適