土下座しながら探索中

主に競技プログラミング

SRM 691 Div1 easy : Sunnygraphs

問題概要 :
n個の頂点とn本の無向辺があり、頂点は0からn-1まで番号が割り振られている
また、辺は頂点iから頂点a[i]に向けて貼られている ( ただし、i != a[i] )

このグラフに対して次の処理を行う
1. 新たな頂点 n を追加する
2. 0からn-1までの頂点集合から任意の部分集合Mを選ぶ
3. Mに属する頂点 i について、辺(i,a[i])をグラフから取り除く
4. Mに属する頂点 i について、辺(i,n)をグラフに追加する

この処理を行ったあと、0から1へのパスが存在するようなMの選び方は何通り存在するか?

解法 :
グラフの取りうる状態について考える
グラフの状態は初期状態で0と1の間にパスが存在するかしないかで分けられるため、それぞれについて考えていく
今後、説明上どの頂点からどの頂点に向けて辺が貼られているのかを明らかにするためグラフの辺は有向辺として書くが実際は無向辺であるので注意すること

まず、0と1の間にパスが存在しない場合のグラフは次のようになる
f:id:tei3344:20160531024608j:plain
このグラフは0から到達可能な頂点集合(上の図では頂点0,2)と1から到達可能な頂点集合(上の図では頂点1,3)、それ以外の頂点集合(上の図では頂点4,5)から成る
それ以外の頂点集合は空集合でも良い
0と1の間にパスをつくるためには、
0から到達可能な頂点集合から少なくとも1つ、
1から到達可能な頂点集合から少なくとも1つの頂点をMとして選ぶ必要がある
f:id:tei3344:20160531025416p:plain
0と1から到達可能な頂点集合からそれぞれ少なくとも1つの頂点をMとして選んだのであれば、
それ以外の頂点集合はMに追加してもしなくてもどちらでもよい
これより、0と1の間にパスが存在しない場合の答えは (2^(0から到達可能な頂点集合の大きさ)-1) * (2^(1から到達可能な頂点集合の大きさ)-1) * (2^(それ以外の頂点集合の大きさ))で求めることができる
答えの式中にある-1は1つも頂点を選ばない場合を取り除くためのものである

次に、0と1の間にパスが存在する場合のグラフについて考える
このときグラフは次のようになる
f:id:tei3344:20160531031045p:plain
このグラフの頂点集合は次のように分類することができる
0と1のそれぞれから探索を開始したとき、

\* 0からのみ到達可能な頂点集合 ( 上の図では頂点0,2 )
\* 1からのみ到達可能な頂点集合 ( 上の図では頂点1,4)
\* 両方から到達可能な頂点集合 ( 上の図では頂点3,5,6)
\* 両方から到達不可能な頂点集合( 上の図では頂点7,8 )
このグラフはすでに0と1の間にパスが存在するため、そのパスを壊さないような頂点Mの選び方が答えとなる

パスを壊さないような頂点の選び方は次の5通りである
\* 0からのみ到達可能な頂点集合と1からのみ到達可能な頂点集合から少なくとも1つは頂点をMとして選ぶ
f:id:tei3344:20160531031733p:plain
このとき、両方から到達可能、到達不可能な頂点集合からは頂点をMとして選んでも選ばなくても良い
そのため、このときのMの選び方は(2^(0から到達可能な頂点集合の大きさ)-1) * (2^(1から到達可能な頂点集合の大きさ)-1) * (2^(両方から到達可能な頂点集合の大きさ)) * (2^(両方から到達不可能な頂点集合の大きさ))となる


\* 0からのみ到達可能な頂点集合から少なくとも1つは頂点をMとして選ぶ, 1からのみ到達可能な頂点集合からは1つも選ばない
f:id:tei3344:20160531032412j:plain
これだけでは0と1の間にパスができないため、両方から到達可能な頂点集合から少なくとも1つはMとして選ぶ必要がある
そのため、このときのMの選び方は(2^(0から到達可能な頂点集合の大きさ)-1) * (2^(両方から到達可能な頂点集合の大きさ)-1) * (2^(両方から到達不可能な頂点集合の大きさ))となる

\* 1からのみ到達可能な頂点集合から少なくとも1つは頂点をMとして選ぶ, 0からのみ到達可能な頂点集合からは1つも選ばない
f:id:tei3344:20160531032728j:plain
これだけでは0と1の間にパスができないため、両方から到達可能な頂点集合から少なくとも1つはMとして選ぶ必要がある
そのため、このときのMの選び方は(2^(1から到達可能な頂点集合の大きさ)-1) * (2^(両方から到達可能な頂点集合の大きさ)-1) * (2^(両方から到達不可能な頂点集合の大きさ))となる

\* 0からのみ到達可能な頂点集合と1からのみ到達可能な頂点集合からは頂点を1つも選ばない、両方から到達可能な頂点集合から少なくとも1つはMとして選ぶ
f:id:tei3344:20160531032923j:plain
0からのみ到達可能な頂点集合と1からのみ到達可能な頂点集合からは1つも頂点をMとして選んでいないため、0と1の間にはパスが残ったままである
そのため、このときのMの選び方は(2^(両方から到達可能な頂点集合の大きさ)-1) * (2^(両方から到達不可能な頂点集合の大きさ))となる

\* 両方から到達不可能な頂点集合からのみ頂点をMとして選ぶ
f:id:tei3344:20160531033302j:plain
このときのMの選び方は(2^(両方から到達不可能な頂点集合の大きさ))となる

これら5通りの選び方の総和が答えとなる

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;
typedef long long ll;

vector<int> G[100],checkG[100];

typedef pair<int,int> ii;

inline void fix(ii &v) { if(v.first > v.second) swap(v.first,v.second); }

void dfs(int cur,map<ii,ll> &mp) {
  rep(i,(int)G[cur].size()) {
    ii edge = ii(cur,G[cur][i]);
    if( mp.count(edge) ) continue;
    ++mp[edge];
    dfs(G[cur][i],mp);
  }
}

bool used[100];
bool checkDFS(int cur) {
  if( cur == 1 ) return true;
  bool res = false;
  rep(i,(int)checkG[cur].size()) {
    int &next = checkG[cur][i];
    if( used[next] ) continue;
    used[next] = true;
    res |= checkDFS(next);
  }
  return res;
}

class Sunnygraphs {
public:
  long long count(vector <int> a) {
    rep(i,(int)a.size()) {
      G[i].push_back(a[i]);
      checkG[i].push_back(a[i]);
      checkG[a[i]].push_back(i);
    }
    map<ii,ll> counter0,counter1;
    dfs(0,counter0);    
    dfs(1,counter1);
    long long zero = (long long)counter0.size();
    long long one  = (long long)counter1.size();
    long long otherwise = (int)a.size();
    if( !checkDFS(0) ) {
      otherwise -= ( zero + one );
      return ((1LL<<zero)-1LL) * ((1LL<<one)-1LL) * (1LL<<otherwise);
    }
    long long common = 0, answer = 0;
    for(map<ii,ll>::iterator it=counter0.begin();it!=counter0.end();it++) {
      ii v = it->first;
      if( counter1.count(v) ) {
	++common;
      }
    }
    zero -= common, one -= common;
    otherwise -= ( zero + one + common);
    if( zero && one ) {
      answer += ( ((1LL<<zero)-1LL) * ((1LL<<one)-1LL) * (1LL<<common) * (1LL<<otherwise) );
    }
    if( zero ) {
      answer += ( ((1LL<<common)-1LL) * ((1LL<<(zero))-1LL) * (1LL<<otherwise) );
    }
    if( one ) {
      answer += ( ((1LL<<common)-1LL) * ((1LL<<(one))-1LL) * (1LL<<otherwise) );
    }
    if( common ) {
      answer += ((1LL<<common)-1LL) * (1LL<<otherwise);
    }
    answer += (1LL<<otherwise);
    return answer;

  }
};