Network Wars

07年胡伯涛的论文上的题：http://wenku.baidu.com/view/87ecda38376baf1ffc4fad25.html

代码：

#include <algorithm>

#include <cstdio>

#include <iterator>

#include <limits>

#include <vector>

#include <string.h>

const int N = 111;

const int M = 404;

const double EPS = 1e-3;

typedef std::vector<int> VI;

int signum(double x) {

    return x > EPS ? 1 : (x < -EPS ? -1 : 0);

}

template<int N, int M, class Flow>

struct Dinic {

    int n, e, first[N], cur[N], next[M], to[M], id[M], s, t;

    int pre[N], level[N], q[N], sign;

    Flow cap[M], flow;

    void add(int u, int v, Flow w, int i) {

        to[e] = v;

        cap[e] = w;

        id[e] = i;

        next[e] = first[u];

        first[u] = e++;

    }

    bool bfs(int s, int t) {

        std::fill(level+1, level + n + 1, -1);

        sign = t;

        level[t] = 0;

        int head = 0, tail = 0;

        q[tail++] = t;

        while (head != tail && level[s] == -1) {

            int u = q[head++];

            for (int it = first[u]; it != -1; it = next[it]) {

                if (cap[it ^ 1] > 0 && level[to[it]] == -1) {

                    level[to[it]] = level[u] + 1;

                    q[tail++] = to[it];

                }

            }

        }

        return level[s] != -1;

    }

    void push() {

        Flow delta = std::numeric_limits<Flow>::max();

        int u, p;

        for (u = t; u != s; u = to[p ^ 1]) {

            p = pre[u];

            delta = std::min(delta, cap[p]);

        }

        for (u = t; u != s; u = to[p ^ 1]) {

            p = pre[u];

            cap[p] -= delta;

            if (!cap[p]) {

                sign = to[p ^ 1];

            }

            cap[p ^ 1] += delta;

        }

        flow += delta;

    }

    void dfs(int u) {

        if (u == t) {

            push();

        } else {

            for (int & it = cur[u]; it != -1; it = next[it]) {

                if (cap[it] > 0 && level[u] == level[to[it]] + 1) {

                    pre[to[it]] = it;

                    dfs(to[it]);

                    if (level[sign] > level[u]) {

                        return;

                    }

                    sign = t;

                }

            }

            level[u] = -1;

        }

    }

    void init(int _n, int _s, int _t) {

        n = _n, s = _s, t = _t;

        std::fill(first + 1 , first + n + 1 , -1);

        e = 0;

    }

    Flow solve() {

        flow = 0;

        while (bfs(s, t)) {

            for (int i = 1; i <= n; ++i) {

                cur[i] = first[i];

            }

            dfs(s);

        }

        return flow;

    }

};

Dinic<N,M<<1,double> AC ;

int left[M] , right[M] , w[M] ;

int n , m , mark[M] ;

double judge ( double key ) {

    double sum = 0 ;

    memset ( mark , 0 , sizeof ( mark ) ) ;

    AC.init ( n , 1 , n ) ;

    for ( int i = 1 ; i <= m ; i ++ )

        if ( w[i] <= key ) {

            sum += w[i] - key ;

            mark[i] = 1 ;

        } else {

            AC.add ( left[i] , right[i] , w[i] - key , i ) ;

            AC.add ( right[i] , left[i] , w[i] - key , i ) ;

        }

    double add = AC.solve () ;

    sum += add ;

    return sum ;

}

void solve () {

    double l = 0 , r = (double) m * 1e7 ;

    while ( signum (r-l) > 0 ) {

        double mid = ( l + r ) / 2.0 ;

        double k = judge ( mid ) ;

        if ( signum ( k ) >= 0 ) l = mid ;

        else r = mid ;

    }

    AC.bfs ( 1 , n ) ;

    for ( int i = 0 ; i < AC.e ; i ++ ) {

        int u = AC.to[i^1] , v = AC.to[i] ;

        if ( AC.level[u] == -1 && AC.level[v] != -1 )

        mark[AC.id[i]] = 1 ;

    }

    int ans = 0 ;

    for ( int i = 1 ; i <= m ; i ++ ) if ( mark[i] ) ans ++ ;

    printf ( "%d\n" , ans ) ;

    for ( int i = 1 ; i <= m ; i ++ ) if ( mark[i] ) printf ( "%d " , i ) ;

    puts ( "" ) ;

}

int main () {

 //   freopen("network.in", "r", stdin);

 //   freopen("network.out", "w", stdout);

    int flag = 0 ;

    while ( scanf ( "%d%d" , &n , &m ) != EOF ) {

        for ( int i = 1 ; i <= m ; i ++ )

            scanf ( "%d%d%d" , &left[i] , &right[i] , &w[i] ) ;

        if ( flag ) puts ( "" ) ;

        flag = 1 ;

        solve () ;

    }

    return 0 ;

}