Artifact Content
Not logged in

Artifact 3f97582085a591c3d90e95880285684c3916c497


//----------------------------------------------------------------------------
// Goldberg(-Tarjan?) 法 (最大流)
//
// 容量付きグラフ G 上での Src から Dest への最大流量を求める
//   - グラフは隣接行列で渡すこと。G は破壊されます。
//   - 流量だけでなくFlow自体が欲しいときは G の容量が減ってる部分を見る
//
// 計算量は
//   - O(V^3)
//       # 証明はまだ理解していない
//
// アルゴリズムの概略
//   基本形は以下の通り
//      1. とりあえずSrcから出てる辺全部に容量限界まで流す
//      2. 流入 > 流出 なノードを見つけてバランスを取る
//          - そこからDestまで到達するパスがあるなら、より
//            Destに近い方向へ進む辺への流出量を増やす
//          - ないなら、よりSrcへ近い方向から来る辺からの
//            流入量を減らす
//      3. 2.をアンバランスな頂点がなくなるまで繰り返す
//   「流入 > 流出 なノードを見つけて」の処理は、流出入バランスを変えた時に
//   Queueに突っ込んでおくことでFIFOでやる。
//   「Destに近い方向」「Srcに近い方向」を常に厳密に評価する必要はなくて、
//   ある程度の近似でも十分。下のコードではその近似値を d[] で持っている。
//   d[] の評価を適度にちゃんとやったりするheuristicsで速くなるらしい。
//   というかやらないと実際上は使い物にならないらしい。あとでちゃんとやる。
//----------------------------------------------------------------------------

#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   : 流入量 - 流出量
	vector<int>      d( G.size() ); // distance : Destへの距離||Srcへの距離-Nの下限
	d[Src] = G.size();

	queue<Vert> Q; // e[v]>0 なノードを入れておくキュー

	// とりあえずSrcから全力で流す
	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 なノードがなくなるまで繰り返す
	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] ) // 適切な方向に流す "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 ) // バランス取れたのでキューから除く
			Q.pop();
		else // バランス取れてないのはおかしいので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;
	}
}