Codeforces 147B-Smile House - しおしおたのブログ

This problem statement source is Codeforces(http://codeforces.com).
この問題文はCodeforcesのものです。

147B Smile House

http://www.codeforces.com/problemset/problem/147/B

B. Smile House

スマイルハウスは雰囲気を盛り上げるために創られた。
それはｎ個の部屋がある。
部屋同士ドアでつながっているものもある。
ドアで接続されているそれぞれの部屋のペアについて（番号i, j）Petyaは値cijをを知っている。
その値は彼が部屋iから部屋jに移動したときに加算される値である。

Petyaはある巡回する経路に沿って動くことによって彼の雰囲気を無限大にすることができるのではないか、と考えた。
そしてできるなら、ひとつの経路を巡回するのに必要な最小の部屋の数はいくらだろうと考えた。

Input

最初の行は２つの正整数n,mを含む。(1 <= n <= 300, 0 <= m <= n*(n-1)/2 ) ここで、nはスマイルハウスの部屋の数、mはドアの数です。
そしてドアに関する情報が続きます。
m行はそれぞれ４つの整数i, j, Cij, Cjiを含みます(1<=i, j<= n, i!= j, -10^4 <= cij, cji <= 10^4)。
同じ部屋のペアをつなぐドアはひとつ以上ないことが保証されます。
部屋が自分自身と接続するようなドアもないことが保証されます。

Output

雰囲気を無限大にすることができる巡回路の経路で訪れる必要がある最小の部屋の数を出力しなさい。

Sample

input
4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3
output
4

解法

二分探索

考えられる最長のサイクルは３００
lg(300) = 8.22...

ここで、
1, 2, 4, 8, 16, 32, 64, 128, 256本のエッジを経由するような経路を
ひとつのエッジとして考えるようなグラフを考える。

それはワーシャルフロイドに手を加えたものを９回繰り返すことで得ることができる。

state[b][i][j] := (エッジ2^b本経由して、iからjに行く最大コスト)	

for b  (0 -> 8 )
    for i (0 -> ノードの数)
       	for j (0　->　ノードの数)
	      for j (0　->　ノードの数)
	      	     state[b+1][i][j] = max(state[b][i][k] + edge[b][k][j], edge[b+1][i][j]);

こうすることによって、state[b][i][j]に必ず2^b本経由したときの最大コストが入り、それを用いれば、2^(b+1)本用いた時も導出できる.

今度は逆に、
256本、　128本、　、、、、　１本　の順に作ったグラフを見てゆく。

Step 1 dp[i][j]を-INF, dp[i][i] を０で初期化する

Step 2 あるグラフに注目する(edge[b][i][j]) ( b: 8 -> 0)

Step 3 tmp[i][j] = dp[i][j]

Step 3 tmp[i][j]にたいして、注目したグラフのエッジでワーシャルフロイドのようなものをかける.

i) dp[i][i]>0であるような状態が存在するとき、
 2^b本も経由するエッジがいらない。

ii) 存在しないとき
 2^b本経由する必要があるため、答えに2^bを加算し、
 tmp[i][j] = dp[i][j]する。

これで、結果的にエッジの本数を二分探索したことになる。

ソース

#include <iostream>
#include <algorithm>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

typedef long long ll;

using namespace std;


const ll N = 301;
const ll INF = (1LL<<50);
const ll B = 10;

int main(){
  ll n, m;
  cin >> n >> m;
  ll edge[B][N][N];
  rep(i, B)rep(j, N)rep(k, N){
    edge[i][j][k] = -INF;
    if(j == k)edge[i][j][k] = 0;
  }
  
  rep(I, m){
    ll i, j, cIJ, cJI;
    cin >> i >> j >> cIJ >> cJI;
    i--;
    j--;
    edge[0][i][j] = cIJ;
    edge[0][j][i] = cJI;
  }
  rep(b, B-1){
    rep(k, n){
      rep(i, n){
	rep(j, n){
	  edge[b+1][i][j] = max(edge[b][i][k] + edge[b][k][j], edge[b+1][i][j]);
	  
	}
      }
    } 
  }
  
  ll dp[N][N];
  ll ans = 0;
  ll tmp[N][N];
  bool exist = false;
  rep(i, N){
    rep(j, N){
      dp[i][j] = -INF;
      if(i == j)dp[i][j] = 0;
    }
  }
  
  for(int b = B-1; b>=0; b--){
   
    rep(i, N)rep(j, N)tmp[i][j] = -INF;
    rep(k, n){
    
      rep(i, n){
	rep(j, n){
	  tmp[i][j] = max(dp[i][k] + edge[b][k][j], tmp[i][j]);
	}
      }

    }

    bool need = true;
    rep(i, n){
      if(tmp[i][i] > 0){
	need = false;
	exist = true;
      }
    }
    if(need){
      rep(i, N){
	rep(j, N){
	  dp[i][j] = tmp[i][j];
	}
      }
      ans += (1LL<<b);
    }
    
  }

  if(exist)cout << ans+1 << endl;
  else cout << 0 << endl;
  return 0;
}