[POJ] 1459 Power Network

題目網址: http://poj.org/problem?id=1459

題意: 給定一個電流網路，包含發電廠、傳輸場、消耗場，且給定每個發電廠能發多少電，每個消耗場能消耗多少電，以及中間的傳輸線路的最大傳輸量，問整個電流網路最大能提供多少電能。



解法: 很明顯是網路流，是經典的網路流模板題。

TAG: Flow Network, MaxFlow, Ford-Fulkerson

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cstdlib>
	using namespace std;
	#define N 105
	#define INF 1e8
	struct Edge {
	int u, v;
	int c;
	int next;
	Edge( int _u = -1, int _v = -1, int _c = 0, int _next = -1 ):
	u(_u), v(_v), c(_c), next(_next) {}
	};
	int n, np, nc, m;
	Edge edge[N*N*10];
	int eCnt;
	int s, t;
	int eHead[N];
	void addEdge( int u, int v, int c )
	{
	edge[eCnt] = Edge( u, v, c, eHead[u] );
	eHead[u] = eCnt++;
	edge[eCnt] = Edge( v, u, 0, eHead[v] );
	eHead[v] = eCnt++;
	}
	void init( void )
	{
	static int i, u, v, c;
	s = n; t = n+1;
	memset( eHead, -1, sizeof(eHead) );
	eCnt = 0;
	for( i = 0; i < m; ++i ) {
	scanf( " (%d,%d)%d", &u, &v, &c );
	addEdge( u, v, c );
	}
	for( i = 0; i < np; ++i ) {
	scanf( " (%d)%d", &v, &c );
	addEdge( s, v, c );
	}
	for( i = 0; i < nc; ++i ) {
	scanf( " (%d)%d", &u, &c );
	addEdge( u, t, c );
	}
	}
	int dinic( void )
	{
	static int i, now, hd, tl, top, flow, nxt, ne, minf;
	static int cur[N], dep[N], que[N];
	flow = 0;
	while( 1 ) {
	memset( dep, -1, sizeof(dep) );
	dep[s] = 0; que[0] = s;
	for( hd=tl=0; hd <= tl && dep[t] == -1; ++hd ) {
	for( now = que[hd], ne = eHead[now]; ne != -1; ne = edge[ne].next ) {
	if( !edge[ne].c || dep[nxt=edge[ne].v] != -1 ) continue;
	dep[nxt] = dep[now]+1;
	que[++tl] = nxt;
	if( nxt == t ) break;
	}
	}
	if( dep[t] == -1 ) break;
	memcpy( cur, eHead, sizeof(cur) );
	now = s; top = 0;
	while( 1 ) {
	if( now == t ) {
	for( minf=INF, i=1; i <= top; ++i ) if( minf > edge[que[i]].c )
	minf = edge[que[tl=i]].c;
	for( i = 1; i <= top; ++i ) {
	edge[que[i]].c -= minf;
	edge[que[i]^1].c += minf;
	}
	now = edge[que[(top=tl)--]].u;
	flow += minf;
	}
	for( ne=cur[now]; ne != -1; ne=cur[now]=edge[ne].next )
	if( edge[ne].c && dep[now]+1 == dep[edge[ne].v] ) break;
	if( cur[now] != -1 ) {
	que[++top] = cur[now];
	now = edge[cur[now]].v;
	} else {
	if( !top ) break;
	dep[now] = -1;
	now = edge[que[top--]].u;
	}
	}
	}
	return flow;
	}
	int main( void )
	{
	int i;
	while( scanf( "%d%d%d%d", &n, &np, &nc, &m ) == 4 ) {
	init();
	printf( "%d\n", dinic() );
	}
	return 0;
	}

view raw Power Network.cpp hosted with ❤ by GitHub