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