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 ;
}