【最大流+dinic】北大 poj 1459 Power Network

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://poj.org/problem?id=1459
    Name  : 1459 Power Network

    Date  : Thursday, February 02, 2012
    Time Stage : 2 hours

    Result: 
9765364	panyanyany
1459
Accepted	332K	125MS	C++
3831B	2012-02-02 15:54:07

Test Data :

Review :
用dinic算法，时间好像还是有点慢～～～
//----------------------------------------------------------------------------*/

#include <cstdio>
#include <CSTRING>

#define MEM(a, v)		memset (a, v, sizeof (a))	// a for address, v for value
#define max(x, y)		((x) > (y) ? (x) : (y))
#define min(x, y)		((x) < (y) ? (x) : (y))

#define INF		(0x3f3f3f3f)
#define MAXN	(103)
#define MAXE	(MAXN*MAXN)

struct EDGE {
	int u, v, c, n ;
};

int		n, m, eCnt, np, nc ;
int		dist[MAXN], vertex[MAXN], q[MAXN] ;

EDGE	edge[MAXE] ;

void init()
{
	eCnt = 0 ;
	MEM(vertex, -1);
	MEM(edge, 0);
}

int findEdge (int u, int v)
{
	int e ;
	for (e = vertex[u] ; e != -1 ; e = edge[e].n)
		if (edge[e].v == v)
			break ;
	return e ;
}

void insert(int u, int v, int c)
{
	int e ;
	if (-1 == (e = findEdge (u, v)))
	{
		edge[eCnt].u = u ;
		edge[eCnt].v = v ;
		edge[eCnt].c += c ;
		edge[eCnt].n = vertex[u] ;
		vertex[u] = eCnt++ ;
		
		// 顺带加上反向边
		edge[eCnt].u = v ;
		edge[eCnt].v = u ;
		edge[eCnt].c += 0 ;
		edge[eCnt].n = vertex[v] ;
		vertex[v] = eCnt++ ;
	}
	else
	{
		edge[e].c += c ;
		edge[e^1].c += 0 ;
	}
}

int dinic (const int beg, const int end)
{
//	printf ("---beg: %d, end: %d---\n", beg, end) ;
	int ans = 0 ;
	while (true)
	{
		int head, tail, u, v, e, i ;
		
		head = tail = 0 ;
		MEM(dist, -1);
		q[tail++] = beg ;
		dist[beg] = 0 ;

		// 构建层次图
//		printf ("\n构建层次图\n") ;
		while (head < tail)
		{
			// 遍历所有与 v 点直接相连的边
			v = q[head++] ;
			for (e = vertex[v] ; e != -1 ; e = edge[e].n)
			{
//				printf ("v:%d e:%d edge: u:%d, v:%d, c:%d, n:%d, dist[%d]:%d + 1 == dist[%d]:%d\n",
//					v, e, edge[e].u, edge[e].v, edge[e].c, edge[e].n, v, dist[v], edge[e].v, dist[edge[e].v]) ;
				if (edge[e].c > 0 && dist[edge[e].v] == -1)
				{
					dist[edge[e].v] = dist[v] + 1 ;
					q[tail++] = edge[e].v ;

					if (end == edge[e].v)
					{
						head == tail ;
						break ;
					}
				}
			}
		}

		// 层次图不能到达汇点
		if (dist[end] == -1)
			break ;

		tail = 0 ;
		v = beg ;
		while (true)
		{
			// 找到一条增广路
			if (end == v)
			{
				int flow, ebreak ;
				flow = INF ;
				// 找到增广路中能够增加的最大流量 flow
				for (i = 0 ; i < tail ; ++i)
				{
					if (flow > edge[q[i]].c)
					{
						flow = edge[q[i]].c ;
						ebreak = i ;
					}
				}
				ans += flow ;
				// 对增广路径中的每条正所边减去 flow，
				// 同时反向边加上 flow
				for (i = 0 ; i < tail ; ++i)
				{
					edge[q[i]].c -= flow ;
					edge[q[i]^1].c += flow ;
				}
				// 下一次寻找增广路就从 v 开始
				v = edge[q[ebreak]].u ;	// 一开始写的 edge[ebreak].u，错到吐……
				tail = ebreak ;
			}

			// 以 v 为增广路径的先头顶点,寻找下一条可增广的边
			for (e = vertex[v] ; e != -1 ; e = edge[e].n)
			{
				if (edge[e].c > 0 && dist[v]+1 == dist[edge[e].v])
					break ;
			}
			
			// 若找不到可增广的边
			if (-1 == e)
			{
				if (tail == 0)	// 增广路径队列中已经没有边了
					break ;
				// 退一条边
				v = edge[q[--tail]].u ;
				// 拆边
				dist[edge[q[tail]].v] = -1 ;
			}
			else // 找到一条可增广的边
			{
				q[tail++] = e ;		// 将其加入队列
				v = edge[e].v ;		// 设置新的先头顶点
			}
		}
	}
	return ans ;
}

int main()
{
	int i, j;
	int u, v, c ;
	while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF)
	{
		init() ;
		for (i = 0 ; i < m ; ++i)
		{
			scanf (" (%d,%d)%d", &u, &v, &c);
			insert (u+1, v+1, c) ;
		}
		for (i = 0 ; i < np ; ++i)
		{
			scanf (" (%d)%d", &u, &c) ;
			insert (0, u+1, c) ;
		}
		for (i = 0 ; i < nc ; ++i)
		{
			scanf (" (%d)%d", &u, &c) ;
			insert (u+1, n+2, c) ;
		}
		printf ("%d\n", dinic(0, n+2)) ;
	}
	return 0;
}