UVA 11478 Halum ( 二分 + 差分約束系統 )

UVa Online Judge
由於順序無關，我們可以將每個操作獨立出來，令 dsum( u ) 為作用在 u 上的所有 d 權和，那麼對於一個邊 u -> v，它的最終邊權是 w( u, v ) + dsum( u ) - dsum( v )。由於題目要求最小值極大化，我們考慮二分搜尋，假設最小值的最大可能為 x，可以列出每個邊 u -> v 都必須滿足的不等式 w( u, v ) + dsum( u ) - dsum( v ) ≥ x，由於二分搜尋可以使 x 為已知，令已知 C = w( u, v ) - x，可以寫成 dsum( u ) + C ≥ dsum( v )，是標準的差分約束系統。在差分約束系統裡，這個不等式等價於一個圖上存在一條有向邊 u -> v 且邊權為 C。可以用 SPFA求是否有負環( 因為這題不保證連通 所以我不確定怎麼求各個 dsum() 否則不難 如1201 -- Intervals )，若存在則不存在有限實數解( 可能無限大，可能無解要另外判斷 )，反之則存在有限實數解。
頭腦不太清楚造了兩個無聊的蟲，一個是想學 LRJ的二分搜( 感覺比較能變化，挺有用的 ) 結果 "while( lb <= ub )"寫成 "while( lb < ub )"，另一個更智障，無解時要求輸出 "No Solution"，我竟輸出 "No solution" 除錯好久。。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MAXN = 500 + 5;
const int MAXM = 2700 + 2;
const int MAXD = 1e4;

int n, m;
vector<pii> G[MAXN];

int dis[MAXN], vis[MAXN], inq[MAXN];
bool hasNegativeCycle(){
    queue<int> que;
    memset( dis, 0, sizeof(dis) );
    memset( vis, 0, sizeof(vis) );
    memset( inq, 0, sizeof(inq) );
    for(int u = 1; u <= n; ++u)
        que.push( u );
    while( !que.empty() ){
        int u = que.front(); que.pop();
        inq[ u ] = 0;
        for(pii &p: G[u]){
            int c = p.first, v = p.second;
            if( dis[ v ] > dis[ u ] + c ){
                dis[ v ] = dis[ u ] + c;
                if( !inq[ v ] ){
                    inq[ v ] = 1;
                    que.push( v );
                    if( ++vis[ v ] > n ) return true;
                }
            }
        }
    }
    return false;
}

bool test(int x){
    for(int u = 1; u <= n; ++u)
        for(pii &p: G[u])
            p.first -= x;
    bool ok = !hasNegativeCycle();
    for(int u = 1; u <= n; ++u)
        for(pii &p: G[u])
            p.first += x;
    return ok;
}

void solve(){
    if( test( MAXD + 1 ) ){
        puts("Infinite"); // can grow infinitely large
        return;
    }
    if( !test( 1 ) ){
        puts("No Solution"); // even the minimum valid is intolerable
        return;
    }
    /* LRJ's binary search
    int ans = 1;
    int lb = 2, ub = MAXD;
    while( lb <= ub ){
        int mid = ( lb + ub ) / 2;
        if( test( mid ) ) ans = mid, lb = mid + 1;
        else ub = mid - 1;
    }
    printf("%d\n", ans);
    */
    int lb = 1, ub = MAXD + 1;
    while( lb + 1 < ub ){
        int mid = ( lb + ub ) / 2;
        if( test( mid ) ) lb = mid;
        else ub = mid;
    }
    printf("%d\n", lb);
}

void init(){
    for(int u = 1; u <= n; ++u)
        G[u].clear();
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 ){
        init();
        while( m-- ){
            int u, v, d; scanf("%d%d%d", &u, &v, &d);
            G[ u ].push_back( pii( d, v ) );
        }
        solve();
    }
    return 0;
}