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