CFR 147 B. Smile House ( Binary Search, Fast Matrix Multiplication, DP, Binary Enumeration )

題意：
給一個圖，邊用四個值表示，( x, y, Cxy, Cyx )，代表 x 至 y 長度是 Cxy，y 至 x 長度是 Cyx。求是否存在一個正環，若存在則輸出最小環的長度。

資料規模：
節點數 1 ≤ N ≤ 300
邊數 0 ≤ M ≤ N * ( N - 1 ) / 2
權值 -1e4 ≤ C ≤ 1e4
保證所有邊 i != j
時限 3000 ms
記憶體 256 MB

解法：
首先，可以用 floyd-warshall 的一種 dp 形式
dp[ i ][ j ][ k ] : 經過 i 個邊後，j 至 k 的最大可能距離
由於轉移式為
dp[ i ][ j ][ k ] = max{ dp[ i - 1 ][ j ][ x ] + dp[ 1 ][ x ][ k ] | j != x and x != k }
符合矩陣轉移需要的性質( 這樣的轉移矩陣特別稱作 Min-plus-Matrix )，可以用矩陣快速冪進行加速。考慮 I ( 單位矩陣 )，如果全部的元素都設為負無限，雖然和定義相符，但也就會不滿足二分搜的性質，ex: 互質的環長度。但如果所有 dp[ t ][ i ][ i ] 都設為 0，那最後當結果的矩陣中任一個 dp[ t ][ i ][ i ] 大於 0 時，便代表存在 t 個邊以內的正環。
如果直接這麼做，會被卡的很妙 ( Before.cpp )，必須將一個 lg N 的複雜度。
考慮二進制枚舉，預處理每一個小於 N ( 最大可能環長度 ) 的 2 的冪次的矩陣，從最大的位數考慮，看是否有沒有必要用它。舉例來說，若 N = 300，可以分別考慮 [ 1, 2, 4, 8, 16, 32, 64, 128, 256 ] 個邊形成的轉移矩陣，先枚舉 256 不用，其他全部都用的情形，是否可以形成環。如果可以，代表答案小於 256，否則大於255 ( 或無解 )。下一個考慮如果沒有 128 是否可以形成環，判斷時加入比 128 大且已被判斷必須有的矩陣，和比 128 小的所有矩陣，依此類推。考慮完所有位元後，再做一次額外的判定確認是否存在環。

時間 / 空間複雜度：
O( N ^ 3 lg N )

閒話：
二進制枚舉其實就是廣義的二分搜，但沒想到還能方便預處理，好題目。

Before:

int N, M;
vvi edge;

void init(){
    cin >> N >> M;
    edge = vvi( N, vi( N, -INF ) );
    for( int i = 0; i < N; ++i )
        edge[ i ][ i ] = 0;
    for( int i = 0; i < M; ++i ){
        int u, v, wgo, wback;
        cin >> u >> v >> wgo >> wback;
        --u, --v;
        edge[ u ][ v ] = wgo;
        edge[ v ][ u ] = wback;
    }
}

vvi mat_mul( vvi a, vvi b ){
    vvi res( a.size(), vi( b[ 0 ].size(), -INF ) );
    for( int i = 0; i < a.size(); ++i )
        for( int j = 0; j < a[ 0 ].size(); ++j )
            for( int k = 0; k < b[ 0 ].size(); ++k ) if( a[ i ][ j ] != -INF and b[ j ][ k ] != -INF )
                upmax( res[ i ][ k ], a[ i ][ j ] + b[ j ][ k ] );
    return res;
}

vvi mat_pow( vvi a, int p ){
    vvi res( a.size(), vi( a.size(), -INF ) );
    for( int i = 0; i < a.size(); ++i )
        res[ i ][ i ] = 0;
    while( p ){
        if( p & 1 )
            res = mat_mul( res, a );
        p >>= 1, a = mat_mul( a, a );
    }
    return res;
}

void solve(){
    int ans = 0;
    int lb = 1, rb = N;
    while( lb <= rb ){
        int mid = lb + rb >> 1;
        vvi x = mat_pow( edge, mid );
        int ok = 0;
        for( int i = 0; i < N; ++i )
            ok |= x[ i ][ i ] > 0;
        if( ok )
            ans = mid, rb = mid - 1;
        else
            lb = mid + 1;
    }
    cout << ans << endl;
}

After:

typedef tuple< int, int, int, int > t4i;

int N, M;
vector< t4i > C;

void init(){
    cin >> N >> M;
    C = vector< t4i >( M );
    for( int i = 0; i < M; ++i ){
        int x, y, cxy, cyx;
        cin >> x >> y >> cxy >> cyx;
        C[ i ] = make_tuple( x - 1, y - 1, cxy, cyx );
    }
}

int maxp;
vvvi dbl; // doubled path matrix : shortest path matrix for 2 ^ i number of edges path only
vvvi pdbl; // dot product of first i doubled path matrices

vvi I; // identity matrix

vvi mat_mul( vvi a, vvi b ){
    vvi res = I;
    for( int i = 0; i < a.size(); ++i )
        for( int j = 0; j < b.size(); ++j )
            for( int k = 0; k < b[ 0 ].size(); ++k )
                upmax( res[ i ][ k ], a[ i ][ j ] + b[ j ][ k ] );
    return res;
}

void preprocess(){
    I = vvi( N, vi( N, -INF ) );
    for( int i = 0; i < N; ++i )
        I[ i ][ i ] = 0;
    maxp = 32 - __builtin_clz( N )  - 1;
    dbl = pdbl = vvvi( maxp + 1, vvi( N, vi( N ) ) );
    dbl[ 0 ] = I;
    for( int i = 0; i < M; ++i ){
        int x, y, cxy, cyx;
        tie( x, y, cxy, cyx ) = C[ i ];
        dbl[ 0 ][ x ][ y ] = cxy;
        dbl[ 0 ][ y ][ x ] = cyx;
    }
    for( int i = 0; i < maxp; ++i )
        dbl[ i + 1 ] = mat_mul( dbl[ i ], dbl[ i ] );
    pdbl[ 0 ] = I;
    for( int i = 0; i < maxp; ++i )
        pdbl[ i + 1 ] = mat_mul( pdbl[ i ], dbl[ i ] );
}

void solve(){
    int ans = 0;
    vvi pre = I;
    for( int i = maxp; 0 <= i; --i ){
        int ok = 0;
        vvi cur = mat_mul( pre, pdbl[ i ] );
        for( int j = 0; j < N; ++j )
            ok |= cur[ j ][ j ] > 0;
        if( not ok )
            ans |= 1 << i,
            pre = mat_mul( pre, dbl[ i ] );
    }
    int ok = 0;
    for( int i = 0; i < N; ++i )
        ok |= pre[ i ][ i ] > 0;
    if( not ok )
        cout << 0 << endl;
    else
        cout << ans << endl;
}