ネットワーク・ストリームの最大ストリーム

最大ストリームアルゴリズムはネットワークストリームの基礎となるアルゴリズムであり,EK,Dinic,sapなど,解決策は数多くあるが,ここではEKアルゴリズムを紹介する.
ソースポイントsから広さを優先してtへのパスを探し、このパスの最大流量(短板効果)lを算出し、遡及し、このパスの各エッジの最大流量をlから減算し、逆エッジを追加し、容量はl、ネットワークストリームの最大ストリームmax+=lとする.sからtへの経路が見つからない場合に終了し、最大流量はmaxである.
EKテンプレート:

#include <iostream>
#include <queue>
using namespace std;
const int N = 202;
const int INF = 0x7fffffff;
queue<int> q;
int n,m;		//m   ( 1 m)，n   
int start,end;

int map[N][N];
int path[N];		//       
int flow[N];		//                    

int bfs()
{
	int i,t;
	while(!q.empty()) q.pop();
	memset(path,-1,sizeof(path));
	path[start] = 0, flow[start] = INF;			//     
	q.push(start);
	while(!q.empty())
	{
		t = q.front();
		q.pop();
		if(t == end) break;						//    &&  end    
		for(i = 1; i <= m; i++)					// t       (t,i),  i   
		{
			if(i!=start && path[i]==-1 && map[t][i])
			{
				flow[i] = flow[t] < map[t][i] ? flow[t] : map[t][i];	// (t,i)   
				q.push(i);
				path[i] = t;
			}
		}
	}
	if(path[end] == -1)
		return -1;
	return flow[end];			//           (      )
}

int Edmonds_Karp()
{
	int max_flow = 0;
	int step,now,pre;
	while((step=bfs())!=-1)				//        
	{
		max_flow += step;
		now = end;
		while(now != start)
		{
			pre = path[now];
			map[pre][now] -= step;		//          (         ，    ，    )
			map[now][pre] += step;		//     
			now = pre;
		}
	}
	return max_flow;
}

int main()
{
	int i,a,b,cost;
	while(scanf("%d %d",&n,&m) != EOF)
	{
		memset(map,0,sizeof(map));
		for(i = 0; i < n; i++)
		{
			scanf("%d %d %d",&a,&b,&cost);
			map[a][b] += cost;				//          
		}
		start = 1, end = m;
		printf("%d
",Edmonds_Karp());
	}
	return 0;
}

実際には、ネットワークが知られている場合、最大ストリームを求めるのは非常に簡単で、テンプレートを直接使用すればいいのですが、図面を構築するのは難しいことがよくあります.テーマの説明を単源単汇のネットワークに変換する方法は、以下にいくつかのテーマを列挙します.
POJ1459
n個の発電所があって、m個の変圧器、c個の消費者、発電所は電気エネルギーを消費しないで、消費者は電気エネルギーを発生しないで、変圧器は電気エネルギーを発生しないで、電気エネルギーを消費しません.発電所ごとに最大の発電量があり、消費者も最大の消費量があり、2点間の線路ごとに最大の容量がある.このネットワークの最大トラフィック(明らかに、ネットワーク全体において、発生電力=消費電力)が要求される.
分析:明らかにこれは多源多匯のネットワークモデルであり、以下の転化を行うことができる:1つのスーパーソースsを増加し、それは各発電所と1本の線を接続し、容量は発電所の最大発電量であり、1つのスーパーポイントtを増加し、各消費者はそれと1本の線を接続し、容量は消費者の最大消費量である.これにより,問題は,このような単一ソース単一送金を求める単純なネットワークストリームに変換される.
POJ1149
1つの养豚场はnつの豚の部屋があって、すべての豚の部屋は无限に多くの豚を入れることができて、すべての顾客はすべて特定の豚の部屋の键と购入量があって、すべての顾客は买った后に再び开いた豚の部屋をロックして、しかしロックする前にある豚の部屋の豚をいくつか别の豚の部屋に分けることができます(つまり开いた豚の部屋の间で互いに数量を调整することができます)、豚をいくらまで売れるかを聞く.
分析:顧客をノードとして、ソースsと送金tを増やすことができます.もしこの顧客が豚の部屋の鍵を持っている最初の人であれば、ソースから1つの辺を接続してその顧客に着きます.最初の人でなければ、前の豚の部屋の鍵を持っているお客様は、そのお客様に縁を結んで、容量は無限です.各顧客から1つのエッジをtに接続し、容量はその顧客の購入量である.これにより、単純なネットワークストリームに変換されます.