さいだいネットワークフローアルゴリズム
1、ネットワークフローの基礎
2、FFアルゴリズム実現
3、ffアルゴリズムc++実現
1.ストリームネットワークG=(V,E)は、各エッジ(u,v)∈Eに非負の容量c(u,v)>=0がある方向図である.(u,v)がEに属さない場合、c(u,v)=0とする.ストリームネットワークには、ソースポイントsと集約ポイントtの2つの特別な頂点があります.次の図は、ストリームネットワークの例を示します(斜線の左側の数字は実際のエッジのストリームを表し、右側の数字はエッジの最大容量を表します).
1つのストリームネットワークG=(V,E)に対して,その容量関数はcであり,ソース点とシンク点はそれぞれsとtである.Gのストリームfは,すべてのu,v∈Vに対してf(u,v)<=c(u,v)を要求する容量制限の3つの性質を満たす.反対称性:すべてのu,v∈Vに対して,f(u,v)=−f(v,u)を要求する.ストリーム保存性:すべてのu∈V−{s,t}に対してΣf(u,v)=0(v∈V)が要求される.
容量制限は、1つの頂点から別の頂点へのネットワークストリームが設定された容量を超えてはならないことを示し、1つのパイプが一定の容量の水しか伝送できず、パイプの体積の制限を超えてはならないようだ.反対称性は、頂点uから頂点vへの流れがその逆流で負を求めるものであることを説明し、参照方向が固定された後、異なる方向に立って見ると、速度が正と負のようになる.一方、ストリーム保存性は、非ソースポイントまたは非集約ポイントの頂点から出発するポイントネットワークストリームの和が0であることを示しており、これはキルホフ電流法則に似ており、キルホフ電流法則とは何であれ、通俗的には頂点に入る流量は、その頂点から出る流量に等しく、この式が成立しなければ、必ずその頂点に集積または枯渇する場合があり、このような場合、ストリームネットワークに現れるべきではないので、一般的な最大ストリーム問題は、上記の原則に背かない上で、ソース点sから集約点tまでの最大のトラフィック値を求めることであり、このトラフィック値は、ソース点からの総トラフィックまたは最終的にtに集約された総トラフィックとして定義されるべきであることが明らかである.すなわち、ストリームfの値は|f|=Σf(s,v)(v∈V)と定義される.
2.最大ストリームの問題を解く前に,残留ネットワーク,拡張経路,切断の3つの概念を理解しなければならない.以下に、この3つの概念の基本的な内容を示します.a.与えられたストリームネットワークG=(V,E)において、fをGのうちの1つのストリームとし、1対の頂点u,v∈Vを考察し、容量c(u,v)を超えない条件下でuからvまでの間に押し込むことができる余分なネットワーク流量は、(u,v)の残留容量であり、あるパイプの水がパイプの上限を超えていないように、このパイプについては、きっともっと水を注ぐことができます.残留容量は、cf(u,v)=c(u,v)−f(u,v)と定義される.Gに属する全てのエッジの残留容量からなる帯域重み有向図がGの残留ネットワークである.次の図は、上のストリームネットワークに対応する残留ネットワークです.
残りのネットワークのエッジは、Eのエッジであってもよいし、逆のエッジであってもよい.2つのエッジ(u,v)および(v,u)のうち、少なくとも1つのエッジが初期ネットワークに現れる場合にのみ、エッジ(u,v)は残留ネットワークに現れる.以下に、fがGの1つのストリームであり、GfがGから導出された残留ネットワークであり、f'がGfの1つのストリームである場合、f+f'はGの1つのストリームであり、その値|f+f'|=|f|+|f'|f'|である.証明は,f+f′というストリームがGにおいて前述した3つの原則を満たすことを証明すればよい.ここでは理解性の証明のみが与えられ、1つのパイプを流れる水の総流量がfであり、そのパイプの残りの流量の中に1つの流f'がパイプの残りの流量を超えない最大限界を満たすことができれば、fとf'を合併した後もパイプの総流量を超えず、合併後の総流量値も必ず|f|+|f'|であることが想像できる.
b.拡張経路pは、残留ネットワークGfにおけるsからtまでの単純な経路である.残留ネットワークの定義によれば、G内の対応する拡張経路上の各エッジ(u,v)は、容量制限に違反しない条件下で、uからvへの追加の正のネットワークストリームを収容することができる.この経路上で可能なネットワークストリームの最大値は、p中辺の残留容量の最小値に違いない.これは、p上のストリームがあるエッジ上の残留容量よりも大きい場合、必ずこのエッジ上にストリームが集まる場合があるため、理解しやすい.したがって,最も多くのpの残留ネットワークをcf(p)=min{cf(u,v)|(u,v)がp上}と定義する.一方、従来の残留ネットワークにおける定理によれば、pは残留ネットワークにおけるsからtへの経路であり、|f'|=cf(p)であるに違いないので、Gにおけるストリームfが既知であれば、|f|+|cf(p)|>|f|があり、|f|+|cf(p)|は容量制限を超えない.
c.ストリームネットワークG(V,E)の割(S,T)は,VをSとT=V−Sの2つの部分に分割し,s∈S,t∈Tとする.fが1つのストリームである場合、割(S,T)を通る正味ストリームは、f(S,T)=Σf(x,y)(x∈S,y∈T)と定義され、割(S,T)の容量はc(S,T)である.1つのネットワークの最小割合は、ネットワーク内のすべての割合の中で最小容量を有する割合である.fをGのうちの1つのストリームとし、かつ(S,T)をGのうちの1つの割とすると、割(S,T)の純流f(S,T)=|f|となる.f(S,T)=f(S,V)−f(S,S)=f(S,V)=f(s,V)+f(S−s,V)=f(s,V)=f(s,V)=|f|(ここでの式はf(X,Y)=Σf(x,y)(x∈X,y∈Y)の定義と,前述の3つの制限が打ち出せるはずなので,ここでは詳しくは述べない).以上の定理から,流れを大きくすると,流れfの値|f|が最小割の容量に等しくなるまで絶えず近づき,このとき流れfをさらに大きくすることができれば,fは必ずある最小割の容量を超え,f(S,T)<=c(S,T)が存在することが分かる.
以上述べたように,最大流の最小割合の定理として重要な定理がある.
fがソースsとシンクtを有するストリームネットワークG=(V,E)のストリームである場合、以下の条件は等価である:1)fはGの最大ストリームである.2)残留ネットワークGfは、拡張パスを含まない.3)Gのある割(S,T)に対して,|f|=c(S,T)がある.
ここまでネットワークストリームの基本知識はあまり話されていませんが、次の編では、ネットワーク最大ストリームを解く基本思想と実現を実現するためのいくつかのアルゴリズムを示します.
アルゴリズム導論では最大流問題を解くための一般的な解決法を与えたが,具体的な実現には関与しなかった.ここで私はやはり再び最大流を解く思想を一般的に説明して、それから具体的な実現を与えます.
Ford‐Fulkerson法は3つの重要な思想に依存し,この3つの思想は前のネットワークストリームの基礎の中で述べた:残留ネットワーク,拡張経路と割.Ford‐Fulkerson法は反復法である.開始時,すべてのuに対してv∈Vはf(u,v)=0,すなわち初期状態時流の値は0である.反復のたびに、[拡張パス](Extend Path)を探してストリーム値を増やすことができます.拡張経路は、ソース点sから集約点tまでの間の経路と見なすことができ、この経路に沿ってより多くのストリームを圧入することができ、それによってストリームの値を増加させることができる.この過程は,拡張経路が探し出されるまで繰り返され,最大流の最小割合の定理によれば,拡張経路が含まれていない場合,fはGの最大流である.アルゴリズム導論で与えられたFord‐Fulkerson実装コードは以下の通りである.
FORD_FULKERSON(G,s,t) 1 for each edge(u,v)∈E[G] 2 do f[u,v] 3 f[v,u] 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) 6 for each edge(u,v) in p 7 do f[u,v]//拡張経路上の順方向のエッジに対して、増加したストリーム8 f[v,u]//逆方向のエッジを加えて、反対称性によって求める
1~3行目は各辺のストリームを0に初期化し、4~8行目は、残存ネットワークGfにおいて広がり経路を探索し続け、広がり経路が見つからないまで広がり経路の方向に沿ってストリームの値を更新することである.最後の最大ストリームは、増加するたびに増加するストリーム値cf(p)の和である.実際の実装では、上記のコードを調整してより良い効果を達成することができます.上記の方法を採用すると、2つの配列を保存し、1つは各辺の容量配列cであり、1つは上の各辺のストリーム値配列fであり、拡張経路で頂点uからvが異なるか否かを判断するとともに、c[u][v]-f[u][v]が0より大きいか否かを判断しなければならないが、拡張経路を探す際に残留ネットワークを検索するため、したがって、残留ネットワークの各エッジの容量を表す配列cを1つだけ保存すればよい.これにより、2~3行の初期化時に、各エッジの残留ネットワークの容量がGの各エッジの容量を初期化する(各エッジの初期ストリーム値が0であるため).一方、更新時には、7~8行の操作を変更し、残存ネットワーク上のエッジ(u,v)に対してc[u][v]-=cf(p)を実行し、その逆のエッジ(v,u)に対してc[v][u]+=cf(p)を実行すればよい.
2、FFアルゴリズム実現
3、ffアルゴリズムc++実現
1.ストリームネットワークG=(V,E)は、各エッジ(u,v)∈Eに非負の容量c(u,v)>=0がある方向図である.(u,v)がEに属さない場合、c(u,v)=0とする.ストリームネットワークには、ソースポイントsと集約ポイントtの2つの特別な頂点があります.次の図は、ストリームネットワークの例を示します(斜線の左側の数字は実際のエッジのストリームを表し、右側の数字はエッジの最大容量を表します).
1つのストリームネットワークG=(V,E)に対して,その容量関数はcであり,ソース点とシンク点はそれぞれsとtである.Gのストリームfは,すべてのu,v∈Vに対してf(u,v)<=c(u,v)を要求する容量制限の3つの性質を満たす.反対称性:すべてのu,v∈Vに対して,f(u,v)=−f(v,u)を要求する.ストリーム保存性:すべてのu∈V−{s,t}に対してΣf(u,v)=0(v∈V)が要求される.
容量制限は、1つの頂点から別の頂点へのネットワークストリームが設定された容量を超えてはならないことを示し、1つのパイプが一定の容量の水しか伝送できず、パイプの体積の制限を超えてはならないようだ.反対称性は、頂点uから頂点vへの流れがその逆流で負を求めるものであることを説明し、参照方向が固定された後、異なる方向に立って見ると、速度が正と負のようになる.一方、ストリーム保存性は、非ソースポイントまたは非集約ポイントの頂点から出発するポイントネットワークストリームの和が0であることを示しており、これはキルホフ電流法則に似ており、キルホフ電流法則とは何であれ、通俗的には頂点に入る流量は、その頂点から出る流量に等しく、この式が成立しなければ、必ずその頂点に集積または枯渇する場合があり、このような場合、ストリームネットワークに現れるべきではないので、一般的な最大ストリーム問題は、上記の原則に背かない上で、ソース点sから集約点tまでの最大のトラフィック値を求めることであり、このトラフィック値は、ソース点からの総トラフィックまたは最終的にtに集約された総トラフィックとして定義されるべきであることが明らかである.すなわち、ストリームfの値は|f|=Σf(s,v)(v∈V)と定義される.
2.最大ストリームの問題を解く前に,残留ネットワーク,拡張経路,切断の3つの概念を理解しなければならない.以下に、この3つの概念の基本的な内容を示します.a.与えられたストリームネットワークG=(V,E)において、fをGのうちの1つのストリームとし、1対の頂点u,v∈Vを考察し、容量c(u,v)を超えない条件下でuからvまでの間に押し込むことができる余分なネットワーク流量は、(u,v)の残留容量であり、あるパイプの水がパイプの上限を超えていないように、このパイプについては、きっともっと水を注ぐことができます.残留容量は、cf(u,v)=c(u,v)−f(u,v)と定義される.Gに属する全てのエッジの残留容量からなる帯域重み有向図がGの残留ネットワークである.次の図は、上のストリームネットワークに対応する残留ネットワークです.
残りのネットワークのエッジは、Eのエッジであってもよいし、逆のエッジであってもよい.2つのエッジ(u,v)および(v,u)のうち、少なくとも1つのエッジが初期ネットワークに現れる場合にのみ、エッジ(u,v)は残留ネットワークに現れる.以下に、fがGの1つのストリームであり、GfがGから導出された残留ネットワークであり、f'がGfの1つのストリームである場合、f+f'はGの1つのストリームであり、その値|f+f'|=|f|+|f'|f'|である.証明は,f+f′というストリームがGにおいて前述した3つの原則を満たすことを証明すればよい.ここでは理解性の証明のみが与えられ、1つのパイプを流れる水の総流量がfであり、そのパイプの残りの流量の中に1つの流f'がパイプの残りの流量を超えない最大限界を満たすことができれば、fとf'を合併した後もパイプの総流量を超えず、合併後の総流量値も必ず|f|+|f'|であることが想像できる.
b.拡張経路pは、残留ネットワークGfにおけるsからtまでの単純な経路である.残留ネットワークの定義によれば、G内の対応する拡張経路上の各エッジ(u,v)は、容量制限に違反しない条件下で、uからvへの追加の正のネットワークストリームを収容することができる.この経路上で可能なネットワークストリームの最大値は、p中辺の残留容量の最小値に違いない.これは、p上のストリームがあるエッジ上の残留容量よりも大きい場合、必ずこのエッジ上にストリームが集まる場合があるため、理解しやすい.したがって,最も多くのpの残留ネットワークをcf(p)=min{cf(u,v)|(u,v)がp上}と定義する.一方、従来の残留ネットワークにおける定理によれば、pは残留ネットワークにおけるsからtへの経路であり、|f'|=cf(p)であるに違いないので、Gにおけるストリームfが既知であれば、|f|+|cf(p)|>|f|があり、|f|+|cf(p)|は容量制限を超えない.
c.ストリームネットワークG(V,E)の割(S,T)は,VをSとT=V−Sの2つの部分に分割し,s∈S,t∈Tとする.fが1つのストリームである場合、割(S,T)を通る正味ストリームは、f(S,T)=Σf(x,y)(x∈S,y∈T)と定義され、割(S,T)の容量はc(S,T)である.1つのネットワークの最小割合は、ネットワーク内のすべての割合の中で最小容量を有する割合である.fをGのうちの1つのストリームとし、かつ(S,T)をGのうちの1つの割とすると、割(S,T)の純流f(S,T)=|f|となる.f(S,T)=f(S,V)−f(S,S)=f(S,V)=f(s,V)+f(S−s,V)=f(s,V)=f(s,V)=|f|(ここでの式はf(X,Y)=Σf(x,y)(x∈X,y∈Y)の定義と,前述の3つの制限が打ち出せるはずなので,ここでは詳しくは述べない).以上の定理から,流れを大きくすると,流れfの値|f|が最小割の容量に等しくなるまで絶えず近づき,このとき流れfをさらに大きくすることができれば,fは必ずある最小割の容量を超え,f(S,T)<=c(S,T)が存在することが分かる.
以上述べたように,最大流の最小割合の定理として重要な定理がある.
fがソースsとシンクtを有するストリームネットワークG=(V,E)のストリームである場合、以下の条件は等価である:1)fはGの最大ストリームである.2)残留ネットワークGfは、拡張パスを含まない.3)Gのある割(S,T)に対して,|f|=c(S,T)がある.
ここまでネットワークストリームの基本知識はあまり話されていませんが、次の編では、ネットワーク最大ストリームを解く基本思想と実現を実現するためのいくつかのアルゴリズムを示します.
アルゴリズム導論では最大流問題を解くための一般的な解決法を与えたが,具体的な実現には関与しなかった.ここで私はやはり再び最大流を解く思想を一般的に説明して、それから具体的な実現を与えます.
Ford‐Fulkerson法は3つの重要な思想に依存し,この3つの思想は前のネットワークストリームの基礎の中で述べた:残留ネットワーク,拡張経路と割.Ford‐Fulkerson法は反復法である.開始時,すべてのuに対してv∈Vはf(u,v)=0,すなわち初期状態時流の値は0である.反復のたびに、[拡張パス](Extend Path)を探してストリーム値を増やすことができます.拡張経路は、ソース点sから集約点tまでの間の経路と見なすことができ、この経路に沿ってより多くのストリームを圧入することができ、それによってストリームの値を増加させることができる.この過程は,拡張経路が探し出されるまで繰り返され,最大流の最小割合の定理によれば,拡張経路が含まれていない場合,fはGの最大流である.アルゴリズム導論で与えられたFord‐Fulkerson実装コードは以下の通りである.
FORD_FULKERSON(G,s,t) 1 for each edge(u,v)∈E[G] 2 do f[u,v] 3 f[v,u] 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) 6 for each edge(u,v) in p 7 do f[u,v]//拡張経路上の順方向のエッジに対して、増加したストリーム8 f[v,u]//逆方向のエッジを加えて、反対称性によって求める
1~3行目は各辺のストリームを0に初期化し、4~8行目は、残存ネットワークGfにおいて広がり経路を探索し続け、広がり経路が見つからないまで広がり経路の方向に沿ってストリームの値を更新することである.最後の最大ストリームは、増加するたびに増加するストリーム値cf(p)の和である.実際の実装では、上記のコードを調整してより良い効果を達成することができます.上記の方法を採用すると、2つの配列を保存し、1つは各辺の容量配列cであり、1つは上の各辺のストリーム値配列fであり、拡張経路で頂点uからvが異なるか否かを判断するとともに、c[u][v]-f[u][v]が0より大きいか否かを判断しなければならないが、拡張経路を探す際に残留ネットワークを検索するため、したがって、残留ネットワークの各エッジの容量を表す配列cを1つだけ保存すればよい.これにより、2~3行の初期化時に、各エッジの残留ネットワークの容量がGの各エッジの容量を初期化する(各エッジの初期ストリーム値が0であるため).一方、更新時には、7~8行の操作を変更し、残存ネットワーク上のエッジ(u,v)に対してc[u][v]-=cf(p)を実行し、その逆のエッジ(v,u)に対してc[v][u]+=cf(p)を実行すればよい.
// ：:http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
#include
#include
#include
using namespace std;
int N,M; // ，
const int maxN=201;
bool visited[maxN];
int pre[maxN]; //
int c[maxN][maxN];
int ans;
void Ford_Fulkerson()
{
while(1)
{
queue q;
memset(visited,0,sizeof(visited));
memset(pre,-1,sizeof(pre));
q.push(0); //
visited[0]=1; //
while(!q.empty())
{
int now=q.front();
if(now==M-1) // ：
break;
q.pop();
for(int i=0;i0;i=pre[i]) // For
{
if(c[pre[i]][i]0;i=pre[i])
{
c[pre[i]][i]-=min; // min
c[i][pre[i]]+=min; // min
}
ans+=min;
}
}
int main()
{
//ifstream cin;
//cin.open("input.txt");
while(cin>>N>>M)
{
int v,s,w;
ans=0;
memset(c,0,sizeof(c));
for(int i=0;i>v>>s>>w;
c[v-1][s-1]+=w;
}
//cin.close();
Ford_Fulkerson();
cout<