UVA 11090 Going in Cycle!! ( 二分 + SPFA判負圈 )

UVa Online Judge
要求平均權值極大化，一個很常用的技巧是假設平均權值為 x，如果我們將全部的值減去 x以上的值，或全部減去 x - 1以下的值，前者和後者的差異在總和小於 0和大於 0。題目特別要求的是環，所以我們發現我們可以二分搜尋最接近正確答案的 x，而判斷一個值 mid是否大於平均權值 x的方式就利用這個技巧和判負環的方式就行了。

#include <bits/stdc++.h>
using namespace std;
typedef pair<double, int> pdi;
const int MAXN = 50 + 5;
const int MAXC = 1e7;
const double INF = 1e10;

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

double dis[MAXN];
int vis[MAXN], inq[MAXN];
bool hasNegativeCycle(){
    memset( vis, 0, sizeof(vis) );
    memset( inq, 0, sizeof(inq) );
    queue<int> que;
    for(int u = 1; u <= n; ++u) // several CCs
        dis[ u ] = 0, que.push( u ); // just push everything together
    while( !que.empty() ){ // because we only want to existence of cycle
        int u = que.front(); que.pop();
        inq[ u ] = 0;
        for(pdi p: G[u]){
            double c = p.first;
            int 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(double x){
    for(int u = 1; u <= n; ++u)
        for(int i = 0; i < G[u].size(); ++i)
            G[u][i].first -= x;
    bool ok = hasNegativeCycle();
    for(int u = 1; u <= n; ++u)
        for(int i = 0; i < G[u].size(); ++i)
            G[u][i].first += x;
    return ok;
}

void solve(){
    double lb = 0, ub = (double)( MAXC + 1 );
    if( !test( ub ) ){
        puts("No cycle found.");
        return;
    }
    while( ub - lb > 1e-3 ){
        double mid = ( ub + lb ) / 2;
        if( test( mid ) ) ub = mid;
        else lb = mid;
    }
    printf("%.2lf\n", lb);
}

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

int main(){
    int T; scanf("%d", &T);
    for(int kase = 1; kase <= T; ++kase){
        scanf("%d%d", &n, &m);
        init();
        for(int i = 0; i < m; ++i){
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            G[ a ].push_back( pdi( c, b ) );
        }
        printf("Case #%d: ", kase);
        solve();
    }
    return 0;
}