Artifact Content
Not logged in

Artifact 3f97582085a591c3d90e95880285684c3916c497


//----------------------------------------------------------------------------
// Goldberg(-Tarjan?) �@ (�ő嗬)
//
// �e�ʕt���O���t G ��ł� Src ���� Dest �ւ̍ő嗬�ʂ����߂�
//   - �O���t�͗אڍs��œn�����ƁBG �͔j�󂳂�܂��B
//   - ���ʂ����łȂ�Flow���̂��~�����Ƃ��� G �̗e�ʂ������Ă镔��������
//
// �v�Z�ʂ�
//   - O(V^3)
//       # �ؖ��͂܂��������Ă��Ȃ�
//
// �A���S���Y���̊T��
//   ��{�`�͈ȉ��̒ʂ�
//      1. �Ƃ肠����Src����o�Ă�ӑS���ɗe�ʌ��E�܂ŗ���
//      2. ���� > ���o �ȃm�[�h�����‚��ăo�����X�����
//          - ��������Dest�܂œ��B����p�X������Ȃ�A���
//            Dest�ɋ߂������֐i�ޕӂւ̗��o�ʂ𑝂₷
//          - �Ȃ��Ȃ�A���Src�֋߂��������痈��ӂ����
//            �����ʂ����炷
//      3. 2.���A���o�����X�Ȓ��_���Ȃ��Ȃ�܂ŌJ��Ԃ�
//   �u���� > ���o �ȃm�[�h�����‚��āv�̏����́A���o���o�����X��ς�������
//   Queue�ɓ˂�����ł������Ƃ�FIFO�ł��B
//   �uDest�ɋ߂������v�uSrc�ɋ߂������v����Ɍ����ɕ]������K�v�͂Ȃ��āA
//   ������x�̋ߎ��ł��\���B���̃R�[�h�ł͂��̋ߎ��l�� d[] �Ŏ����Ă���B
//   d[] �̕]����K�x�ɂ����Ƃ�����肷��heuristics�ő����Ȃ�炵���B
//   �Ƃ��������Ȃ��Ǝ��ۏ�͎g�����ɂȂ�Ȃ��炵���B���Ƃł����Ƃ��B
//----------------------------------------------------------------------------

#include <vector>
#include <queue>
#include <limits>
using namespace std;

typedef int                        Vert;
typedef int                        Capacity;
typedef vector< vector<Capacity> > Graph;

Capacity goldberg_tarjan( Graph& G, Vert Src, Vert Dest )
{
	vector<Capacity> e( G.size() ); // excess   : ������ - ���o��
	vector<int>      d( G.size() ); // distance : Dest�ւ̋���||Src�ւ̋���-N�̉���
	d[Src] = G.size();

	queue<Vert> Q; // e[v]>0 �ȃm�[�h�����Ă����L���[

	// �Ƃ肠����Src����S�͂ŗ���
	for(int v=0; v!=G.size(); ++v)
		if( G[Src][v] )
		{
			G[v][Src] += G[Src][v];
			e[v]      += G[Src][v];
			G[Src][v]  = 0;
			Q.push(v);
		}

	// e[v]>0 �ȃm�[�h���Ȃ��Ȃ�܂ŌJ��Ԃ�
	while( !Q.empty() )
	{
		Vert v = Q.front();

		for(int u=0; u!=G.size() && e[v]; ++u)
			if( G[v][u] && d[v]>d[u] ) // �K�؂ȕ����ɗ��� "PUSH"
			{
				Capacity f = min(e[v], G[v][u]);
				G[v][u] -= f;
				G[u][v] += f;
				e[v] -= f;
				e[u] += f;
				if( e[u]==f && u!=Src && u!=Dest ) Q.push(u);
			}

		if( e[v] == 0 ) // �o�����X��ꂽ�̂ŃL���[���珜��
			Q.pop();
		else // �o�����X���ĂȂ��̂͂��������̂�d[v]�𒲐����Ă�蒼�� "RELABEL"
		{
			Capacity m = numeric_limits<Capacity>::max();
			for(int u=0; u!=G.size(); ++u)
				if( G[v][u] )
					m = min(m, d[u]+1);
			d[v] = m;
		}
	}

	// Dest �ւ̗����ʂ�Ԃ�
	return e[Dest];
}

//----------------------------------------------------------------------------
// PKU 1459
//----------------------------------------------------------------------------

#include <iostream>
#include <locale>

int main()
{
	cin.imbue( std::locale("C") );
	for(int n,np,nc,m; cin>>n>>np>>nc>>m;)
	{
		// 0: src, 1: dst, 2: ...
		Graph g(n+2, vector<Capacity>(n+2));

		while(m--)
		{
			int u, v, z; char _;
			cin >> _ >> u >> _ >> v >> _ >> z;
			g[u+2][v+2] = z;
		}

		while(np--)
		{
			int u, z; char _;
			cin >> _ >> u >> _ >> z;
			g[0][u+2] = z;
		}

		while(nc--)
		{
			int u, z; char _;
			cin >> _ >> u >> _ >> z;
			g[u+2][1] = z;
		}

		cout << goldberg_tarjan(g, 0, 1) << endl;
	}
}