23dfcca431 2011-02-23        kinaba: //----------------------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // Goldberg(-Tarjan?) 法 (最大流)
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // 容量付きグラフ G 上での Src から Dest への最大流量を求める
23dfcca431 2011-02-23        kinaba: //   - グラフは隣接行列で渡すこと。G は破壊されます。
23dfcca431 2011-02-23        kinaba: //   - 流量だけでなくFlow自体が欲しいときは G の容量が減ってる部分を見る
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // 計算量は
23dfcca431 2011-02-23        kinaba: //   - O(V^3)
23dfcca431 2011-02-23        kinaba: //       # 証明はまだ理解していない
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // アルゴリズムの概略
23dfcca431 2011-02-23        kinaba: //   基本形は以下の通り
23dfcca431 2011-02-23        kinaba: //      1. とりあえずSrcから出てる辺全部に容量限界まで流す
23dfcca431 2011-02-23        kinaba: //      2. 流入 > 流出 なノードを見つけてバランスを取る
23dfcca431 2011-02-23        kinaba: //          - そこからDestまで到達するパスがあるなら、より
23dfcca431 2011-02-23        kinaba: //            Destに近い方向へ進む辺への流出量を増やす
23dfcca431 2011-02-23        kinaba: //          - ないなら、よりSrcへ近い方向から来る辺からの
23dfcca431 2011-02-23        kinaba: //            流入量を減らす
23dfcca431 2011-02-23        kinaba: //      3. 2.をアンバランスな頂点がなくなるまで繰り返す
23dfcca431 2011-02-23        kinaba: //   「流入 > 流出 なノードを見つけて」の処理は、流出入バランスを変えた時に
23dfcca431 2011-02-23        kinaba: //   Queueに突っ込んでおくことでFIFOでやる。
23dfcca431 2011-02-23        kinaba: //   「Destに近い方向」「Srcに近い方向」を常に厳密に評価する必要はなくて、
23dfcca431 2011-02-23        kinaba: //   ある程度の近似でも十分。下のコードではその近似値を d[] で持っている。
23dfcca431 2011-02-23        kinaba: //   d[] の評価を適度にちゃんとやったりするheuristicsで速くなるらしい。
23dfcca431 2011-02-23        kinaba: //   というかやらないと実際上は使い物にならないらしい。あとでちゃんとやる。
23dfcca431 2011-02-23        kinaba: //----------------------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: #include <vector>
23dfcca431 2011-02-23        kinaba: #include <queue>
23dfcca431 2011-02-23        kinaba: #include <limits>
23dfcca431 2011-02-23        kinaba: using namespace std;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: typedef int                        Vert;
23dfcca431 2011-02-23        kinaba: typedef int                        Capacity;
23dfcca431 2011-02-23        kinaba: typedef vector< vector<Capacity> > Graph;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: Capacity goldberg_tarjan( Graph& G, Vert Src, Vert Dest )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	vector<Capacity> e( G.size() ); // excess   : 流入量 - 流出量
23dfcca431 2011-02-23        kinaba: 	vector<int>      d( G.size() ); // distance : Destへの距離||Srcへの距離-Nの下限
23dfcca431 2011-02-23        kinaba: 	d[Src] = G.size();
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	queue<Vert> Q; // e[v]>0 なノードを入れておくキュー
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	// とりあえずSrcから全力で流す
23dfcca431 2011-02-23        kinaba: 	for(int v=0; v!=G.size(); ++v)
23dfcca431 2011-02-23        kinaba: 		if( G[Src][v] )
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			G[v][Src] += G[Src][v];
23dfcca431 2011-02-23        kinaba: 			e[v]      += G[Src][v];
23dfcca431 2011-02-23        kinaba: 			G[Src][v]  = 0;
23dfcca431 2011-02-23        kinaba: 			Q.push(v);
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	// e[v]>0 なノードがなくなるまで繰り返す
23dfcca431 2011-02-23        kinaba: 	while( !Q.empty() )
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		Vert v = Q.front();
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		for(int u=0; u!=G.size() && e[v]; ++u)
23dfcca431 2011-02-23        kinaba: 			if( G[v][u] && d[v]>d[u] ) // 適切な方向に流す "PUSH"
23dfcca431 2011-02-23        kinaba: 			{
23dfcca431 2011-02-23        kinaba: 				Capacity f = min(e[v], G[v][u]);
23dfcca431 2011-02-23        kinaba: 				G[v][u] -= f;
23dfcca431 2011-02-23        kinaba: 				G[u][v] += f;
23dfcca431 2011-02-23        kinaba: 				e[v] -= f;
23dfcca431 2011-02-23        kinaba: 				e[u] += f;
23dfcca431 2011-02-23        kinaba: 				if( e[u]==f && u!=Src && u!=Dest ) Q.push(u);
23dfcca431 2011-02-23        kinaba: 			}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		if( e[v] == 0 ) // バランス取れたのでキューから除く
23dfcca431 2011-02-23        kinaba: 			Q.pop();
23dfcca431 2011-02-23        kinaba: 		else // バランス取れてないのはおかしいのでd[v]を調整してやり直し "RELABEL"
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			Capacity m = numeric_limits<Capacity>::max();
23dfcca431 2011-02-23        kinaba: 			for(int u=0; u!=G.size(); ++u)
23dfcca431 2011-02-23        kinaba: 				if( G[v][u] )
23dfcca431 2011-02-23        kinaba: 					m = min(m, d[u]+1);
23dfcca431 2011-02-23        kinaba: 			d[v] = m;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	// Dest への流入量を返す
23dfcca431 2011-02-23        kinaba: 	return e[Dest];
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: //----------------------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // PKU 1459
23dfcca431 2011-02-23        kinaba: //----------------------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: #include <iostream>
23dfcca431 2011-02-23        kinaba: #include <locale>
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: int main()
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	cin.imbue( std::locale("C") );
23dfcca431 2011-02-23        kinaba: 	for(int n,np,nc,m; cin>>n>>np>>nc>>m;)
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		// 0: src, 1: dst, 2: ...
23dfcca431 2011-02-23        kinaba: 		Graph g(n+2, vector<Capacity>(n+2));
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		while(m--)
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			int u, v, z; char _;
23dfcca431 2011-02-23        kinaba: 			cin >> _ >> u >> _ >> v >> _ >> z;
23dfcca431 2011-02-23        kinaba: 			g[u+2][v+2] = z;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		while(np--)
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			int u, z; char _;
23dfcca431 2011-02-23        kinaba: 			cin >> _ >> u >> _ >> z;
23dfcca431 2011-02-23        kinaba: 			g[0][u+2] = z;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		while(nc--)
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			int u, z; char _;
23dfcca431 2011-02-23        kinaba: 			cin >> _ >> u >> _ >> z;
23dfcca431 2011-02-23        kinaba: 			g[u+2][1] = z;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		cout << goldberg_tarjan(g, 0, 1) << endl;
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: }