Network Wars

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

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           const int N = 111;const int M = 404;const double EPS = 1e-3;typedef std::vector
           
             VI;int signum(double x) { return x > EPS ? 1 : (x < -EPS ? -1 : 0);}template
            
             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
             
              ::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
              
               <<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 ;}