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;
}
}