#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;
struct node {
	int x, y, next, c, opp;
}a[110000]; int first[1100], n, len, m, D, F;
const int Max_int = 0x7fffffff;
int _min ( int x, int y ){ return x < y ? x : y; }
void ins ( int x, int y, int c ){
	int k1, k2;
	len ++; k1 = len;
	a[len].x = x; a[len].y = y; a[len].c = c;
	a[len].next = first[x]; first[x] = len;
	len ++; k2 = len;
	a[len].x = y; a[len].y = x; a[len].c = 0;
	a[len].next = first[y]; first[y] = len;
	a[k1].opp = k2;
	a[k2].opp = k1;
}
int st, ed; int ans;
int h[1100];
bool bfs (){
	memset ( h, -1, sizeof (h) ); h[st] = 1;
	queue <int> q;
	q.push (st);
	while ( !q.empty () ){
		int x = q.front (); q.pop ();
		for ( int k = first[x]; k; k = a[k].next ){
			int y = a[k].y;
			if ( a[k].c > 0 && h[y] == -1 ){
				h[y] = h[x] + 1;
				q.push (y);
			}
		}
	}
	return h[ed] > 0;
}
int dfs ( int x, int flow ){
	if ( x == ed ) return flow;
	int delta = 0;
	for ( int k = first[x]; k; k = a[k].next ){
		int y = a[k].y;
		if ( a[k].c > 0 && h[y] == h[x] + 1 && flow - delta > 0 ){
			int minf = dfs ( y, _min ( a[k].c, flow - delta ) );
			a[k].c -= minf;
			a[a[k].opp].c += minf;
			delta += minf;
		}
	}
	if ( delta == 0 ) h[x] = -1;
	return delta;
}
int lst[1100], vl; bool ved[1100], vst[1100];
void dfs_st ( int x ){
	if ( x <= 0 ) return;
	lst[++vl] = x;
	vst[x] = true;
	for ( int k = first[x]; k; k = a[k].next ){
		int y = a[k].y;
		if ( a[k].c > 0 && vst[y] == false ){
			dfs_st (y);
		}
	}
}
void dfs_ed ( int x ){
	if ( x <= 0 ) return;
	ved[x] = true;
	for ( int k = first[x]; k; k = a[k].next ){
		int y = a[k].y;
		if ( a[a[k].opp].c > 0 && ved[y] == false ){
			dfs_ed (y);
		}
	}
}
int main (){
	freopen ( "a.in", "r", stdin );
	freopen ( "a.out", "w", stdout );
	int i, j, k, x, y;
	len = 0; memset ( first, 0, sizeof (first) );
	scanf ( "%d%d", &n, &m );
	st = 1; ed = n;
	for ( i = 1; i <= m; i ++ ){
		scanf ( "%d%d%d", &x, &y, &k );
		x ++; y ++;
		ins ( x, y, k );
	}
	int sum = 0, delta;
	while ( bfs () ){
		while ( delta = dfs ( st, 0x7fffffff ) ) sum += delta;
	}
	vl = 0;
	memset ( vst, false, sizeof (vst) );
	memset ( ved, false, sizeof (ved) );
	dfs_st (st);
	dfs_ed (ed);
	ans = 0;
	for ( i = 1; i <= vl; i ++ ){
		x = lst[i];
		for ( k = first[x]; k; k = a[k].next ){
			y = a[k].y;
			if ( ved[y] == true && vst[y] == false ) ans ++;
		}
	}
	printf ( "%d\n", ans );
	return 0;
}

• 贡献几组数据 (143) chenyushuo2012 2015-04-10 14:52:59
  • Orz，cys大神…… (0) HWizard 2015-04-10 15:16:02
  • 好人一生平安 (2) 2014lvzelong 2017-07-11 17:08:00