[UVa] 820 - Internet Bandwidth

題目網址: http://goo.gl/3M28qz

題意:
(from luckycat)


解法: 題目已經非常明顯是求 s-t 最大流囉。

TAG: Flow Network, Ford-Fulkerson, MaxFlow

注意

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	#define clr( x, v ) memset( x, v, sizeof(x) )
	#define N 105
	#define INF 1e7
	int n, casei = 1;
	int s, t, c;
	// maximum flow algorithm
	int F[N][N];
	int C[N][N];
	int pre[N], que[N], d[N], mk[N];
	int maxflow( void )
	{
	static int head, tail;
	int i, u, v, flow;
	flow = 0;
	clr( F, 0 );
	do {
	clr( mk, 0 ); clr( d, 0 );
	que[0] = s; mk[s] = 1; d[s] = INF;
	for( pre[s]=head=tail=0; head<=tail && !mk[t]; ++head ) {
	for( u=que[head], v=1; v <= n; ++v ) if( !mk[v] && F[u][v]<C[u][v] ) {
	mk[v] = 1; que[++tail] = v; pre[v] = u;
	if( d[u] < C[u][v]-F[u][v] ) d[v] = d[u];
	else d[v] = C[u][v]-F[u][v];
	}
	}
	if( !mk[t] ) break; flow += d[t];
	for( u=t; u!=s; ) { v = u; u = pre[v]; F[u][v] += d[t]; F[v][u] = -F[u][v]; }
	} while( d[t] > 0 ); return flow;
	}
	int main( void )
	{
	int i, a, b, v;
	while( scanf( "%d", &n ) == 1 && n ) {
	printf( "Network %d\n", casei++ );
	// input & initialization
	scanf( "%d%d%d", &s, &t, &c );
	clr( C, 0 );
	for( i = 1; i <= c; ++i ) {
	scanf( "%d%d%d", &a, &b, &v );
	C[a][b] = C[b][a] += v;
	}
	// solve & output
	printf( "The bandwidth is %d.\n\n", maxflow() );
	}
	return 0;
	}

view raw 820 - Internet Bandwidth.cpp hosted with ❤ by GitHub