4fd800b3a8 2011-02-23        kinaba: //----------------------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // Goldberg(-Tarjan?) �@ (�ő嗬)
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // �e�ʕt���O���t G ��ł� Src ���� Dest �ւ̍ő嗬�ʂ����߂�
4fd800b3a8 2011-02-23        kinaba: //   - �O���t�͗אڍs��œn�����ƁBG �͔j�󂳂�܂��B
4fd800b3a8 2011-02-23        kinaba: //   - ���ʂ����łȂ�Flow���̂��~�����Ƃ��� G �̗e�ʂ������Ă镔��������
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // �v�Z�ʂ�
4fd800b3a8 2011-02-23        kinaba: //   - O(V^3)
4fd800b3a8 2011-02-23        kinaba: //       # �ؖ��͂܂��������Ă��Ȃ�
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // �A���S���Y���̊T��
4fd800b3a8 2011-02-23        kinaba: //   ��{�`�͈ȉ��̒ʂ�
4fd800b3a8 2011-02-23        kinaba: //      1. �Ƃ肠����Src����o�Ă�ӑS���ɗe�ʌ��E�܂ŗ���
4fd800b3a8 2011-02-23        kinaba: //      2. ���� > ���o �ȃm�[�h�����‚��ăo�����X�����
4fd800b3a8 2011-02-23        kinaba: //          - ��������Dest�܂œ��B����p�X������Ȃ�A���
4fd800b3a8 2011-02-23        kinaba: //            Dest�ɋ߂������֐i�ޕӂւ̗��o�ʂ𑝂₷
4fd800b3a8 2011-02-23        kinaba: //          - �Ȃ��Ȃ�A���Src�֋߂��������痈��ӂ����
4fd800b3a8 2011-02-23        kinaba: //            �����ʂ����炷
4fd800b3a8 2011-02-23        kinaba: //      3. 2.���A���o�����X�Ȓ��_���Ȃ��Ȃ�܂ŌJ��Ԃ�
4fd800b3a8 2011-02-23        kinaba: //   �u���� > ���o �ȃm�[�h�����‚��āv�̏����́A���o���o�����X��ς�������
4fd800b3a8 2011-02-23        kinaba: //   Queue�ɓ˂�����ł������Ƃ�FIFO�ł��B
4fd800b3a8 2011-02-23        kinaba: //   �uDest�ɋ߂������v�uSrc�ɋ߂������v����Ɍ����ɕ]������K�v�͂Ȃ��āA
4fd800b3a8 2011-02-23        kinaba: //   ������x�̋ߎ��ł��\���B���̃R�[�h�ł͂��̋ߎ��l�� d[] �Ŏ����Ă���B
4fd800b3a8 2011-02-23        kinaba: //   d[] �̕]����K�x�ɂ����Ƃ�����肷��heuristics�ő����Ȃ�炵���B
4fd800b3a8 2011-02-23        kinaba: //   �Ƃ��������Ȃ��Ǝ��ۏ�͎g�����ɂȂ�Ȃ��炵���B���Ƃł����Ƃ��B
4fd800b3a8 2011-02-23        kinaba: //----------------------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <limits>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: typedef int                        Vert;
4fd800b3a8 2011-02-23        kinaba: typedef int                        Capacity;
4fd800b3a8 2011-02-23        kinaba: typedef vector< vector<Capacity> > Graph;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: Capacity goldberg_tarjan( Graph& G, Vert Src, Vert Dest )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	vector<Capacity> e( G.size() ); // excess   : ������ - ���o��
4fd800b3a8 2011-02-23        kinaba: 	vector<int>      d( G.size() ); // distance : Dest�ւ̋���||Src�ւ̋���-N�̉���
4fd800b3a8 2011-02-23        kinaba: 	d[Src] = G.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	queue<Vert> Q; // e[v]>0 �ȃm�[�h�����Ă����L���[
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	// �Ƃ肠����Src����S�͂ŗ���
4fd800b3a8 2011-02-23        kinaba: 	for(int v=0; v!=G.size(); ++v)
4fd800b3a8 2011-02-23        kinaba: 		if( G[Src][v] )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			G[v][Src] += G[Src][v];
4fd800b3a8 2011-02-23        kinaba: 			e[v]      += G[Src][v];
4fd800b3a8 2011-02-23        kinaba: 			G[Src][v]  = 0;
4fd800b3a8 2011-02-23        kinaba: 			Q.push(v);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	// e[v]>0 �ȃm�[�h���Ȃ��Ȃ�܂ŌJ��Ԃ�
4fd800b3a8 2011-02-23        kinaba: 	while( !Q.empty() )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		Vert v = Q.front();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		for(int u=0; u!=G.size() && e[v]; ++u)
4fd800b3a8 2011-02-23        kinaba: 			if( G[v][u] && d[v]>d[u] ) // �K�؂ȕ����ɗ��� "PUSH"
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				Capacity f = min(e[v], G[v][u]);
4fd800b3a8 2011-02-23        kinaba: 				G[v][u] -= f;
4fd800b3a8 2011-02-23        kinaba: 				G[u][v] += f;
4fd800b3a8 2011-02-23        kinaba: 				e[v] -= f;
4fd800b3a8 2011-02-23        kinaba: 				e[u] += f;
4fd800b3a8 2011-02-23        kinaba: 				if( e[u]==f && u!=Src && u!=Dest ) Q.push(u);
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		if( e[v] == 0 ) // �o�����X��ꂽ�̂ŃL���[���珜��
4fd800b3a8 2011-02-23        kinaba: 			Q.pop();
4fd800b3a8 2011-02-23        kinaba: 		else // �o�����X���ĂȂ��̂͂��������̂�d[v]�𒲐����Ă�蒼�� "RELABEL"
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			Capacity m = numeric_limits<Capacity>::max();
4fd800b3a8 2011-02-23        kinaba: 			for(int u=0; u!=G.size(); ++u)
4fd800b3a8 2011-02-23        kinaba: 				if( G[v][u] )
4fd800b3a8 2011-02-23        kinaba: 					m = min(m, d[u]+1);
4fd800b3a8 2011-02-23        kinaba: 			d[v] = m;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	// Dest �ւ̗����ʂ�Ԃ�
4fd800b3a8 2011-02-23        kinaba: 	return e[Dest];
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: //----------------------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // PKU 1459
4fd800b3a8 2011-02-23        kinaba: //----------------------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <locale>
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: int main()
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	cin.imbue( std::locale("C") );
4fd800b3a8 2011-02-23        kinaba: 	for(int n,np,nc,m; cin>>n>>np>>nc>>m;)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		// 0: src, 1: dst, 2: ...
4fd800b3a8 2011-02-23        kinaba: 		Graph g(n+2, vector<Capacity>(n+2));
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		while(m--)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int u, v, z; char _;
4fd800b3a8 2011-02-23        kinaba: 			cin >> _ >> u >> _ >> v >> _ >> z;
4fd800b3a8 2011-02-23        kinaba: 			g[u+2][v+2] = z;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		while(np--)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int u, z; char _;
4fd800b3a8 2011-02-23        kinaba: 			cin >> _ >> u >> _ >> z;
4fd800b3a8 2011-02-23        kinaba: 			g[0][u+2] = z;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		while(nc--)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int u, z; char _;
4fd800b3a8 2011-02-23        kinaba: 			cin >> _ >> u >> _ >> z;
4fd800b3a8 2011-02-23        kinaba: 			g[u+2][1] = z;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		cout << goldberg_tarjan(g, 0, 1) << endl;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: }