ネットワークフローの詳細
25491 ワード
ネットワークフローの詳細
hehe、詳しく言うと、実際には知識点の不完全なまとめにすぎず、後日補充される可能性がある.
まず、3つの基本的なネットワーク・フローの問題について説明します.
さいだいりゅうもんだい
質問の紹介
これはネットワークストリームの問題の1つであり、最も基本的な1つでもあり、1つのネットワークストリームの中でソースポイントからポイントまで存在できる最大トラフィックを求めることを意味します.この問題には多くのアルゴリズムがありますが、簡単に説明します.
素朴なアルゴリズム
げんり
ほほほ、本当にどこまでも素朴なアルゴリズムがありますね.1つのネットワークストリームについて、私たちはその残量ネットワークの中の拡張路を考慮して、私たちはBFS暴力で探して、それから絶えず拡張して、最後に必ず正しい答えを得ることができて、しかしその効率は非常に低くて、しかもその時間の複雑さは最後の最大ストリームの大きさと関係があって、このようにとても穴があいて、もし私たちが最大ストリームが100000のネットワークを考えるならば、毎回私たちはランダムに拡張路を探しているので、このような状況を構築することができます.このように拡張するには、毎回1単位の流量しか拡張できません.私たちは少なくとも1000000回の拡張が必要で、必ずタイムアウトします.このような書き方はお勧めしません.
コードピット補完
ISAPアルゴリズム
これは私が比較的によく使うアルゴリズムで、その効率はきっと素朴なアルゴリズムよりずっと良くて、最も良いわけではありませんが、しかし大部分のネットの流れの問題にも対処することができます
げんり
実はこのアルゴリズムについて話す前にDinicアルゴリズムをやるべきです.Dinicの改良と言えるからです.しかし、私はDinicを書いたことがありません.原理は知っていますが.ISAPは,拡張後に階層図(Dinicアルゴリズムに対して)を再構築するのではなく,デッドパスが現れるまで拡張路を探し続け,ノードに対してretreat操作を行い,現在デッドパスに入っているノードのd値のみを変更することを考えている.このようにして、私たちは多くの時間を節約することができます(DinicではBFSに相当していますが、もともと多くのリソースの使用空間がありますが、非情に浪費されています).ISAPには効率を向上させる最適化がたくさんありますが、個人的にはISAPアルゴリズムの使用をお勧めします.
ここで、BFSは各ノードから合流点までの最小距離を求めるために用いられ、各アークの長さが1であると仮定するので、BFSを直接走ることができる
拡張するときは、ノードの前のアークに沿って移動するたびに、増分を統計し、再び移動して、この増分を各アークに反映します.
次はコードです
コード#コード#
上のコードの詳細に注意して、それらの多くは注釈でマークされています.また、上のコードが弧を保存するときにvectorを採用しています.効率が悪い場合は、フォワードスターを使用することができます.
もうちょっと...非常に知的障害の詳細は、BFSはstackではなくqueueを使用します.
Dinicアルゴリズム
しばらく書きません
今、私たちは次の問題を研究します.それは..あ、いいえ、もう一つの小さな定理があります.それは最小割最大流の定理です.
さいしょうわりこみさいだいりゅうのていり
この定理は,任意のトラフィックネットワークで求めた最小割合がこのネットワークの最大ストリームに等しいことを意味し,最小割合を解くすべての問題が最大ストリームアルゴリズムを用いて解決できるようにした.
さいしょうわりあてていぎ
最小割合は1つのネットワークを交差しない2つの部分に分けることができる1つのアークの集合であり、私たちはこれらのアークの容量の和をこの割合の容量と呼ぶが、私たちの目的は1つのネットワークの中の1つの容量の最小割合を解くことであり、最小割合と呼ばれ、私たちはこの最小割合の大きさがこのネットワークの最大ストリームに等しいことを証明することができ、複雑ではないことを証明することができる.最小割合定義およびネットワークストリームの性質から証明できる
最小費用最大フローの問題
この問題は比較的実用的な意義を持ち,ネットワークストリーム問題と一般的な図論問題をうまく結びつけた.この問題は、各アークが上記の属性のほかに1つの属性を有する費用付きネットワークに適用される.単位流量の費用は、流量が最大であることを保証する場合に、このネットワーク費用の最小値を求める.
私たちの考えは簡単です.私たちがさっき拡張路を探す方法は相対的に任意なので、その速度が十分に速い限りできますが、この問題では、実行可能な最大ストリームを任意に探すことはできません.新しい制限があり、費用が最も小さいからです.したがって,ネットワークを順次巡回することを考慮することができ,すなわち,費用に関する図を構築し,この図上で最短ルートを走ることによって実現できる.最短のアルゴリズムはSPFAを使うことができて、書くのが便利で走るのが速いです
次はコードです
コード#コード#
この中の注釈の落ちた部分は逆走の最短路と広がりを採用して、同時に本コードはVectorを採用して、時間の効率の要求が厳格であれば前向星に変えることができます
もういいから前向きな星を貼っておこう
上のカード定数の最適化を無視してください
ほかにも、いくつかあるかもしれませんが、今日はちょっと疲れたので、先にここまでやりました.
hehe、詳しく言うと、実際には知識点の不完全なまとめにすぎず、後日補充される可能性がある.
まず、3つの基本的なネットワーク・フローの問題について説明します.
さいだいりゅうもんだい
質問の紹介
これはネットワークストリームの問題の1つであり、最も基本的な1つでもあり、1つのネットワークストリームの中でソースポイントからポイントまで存在できる最大トラフィックを求めることを意味します.この問題には多くのアルゴリズムがありますが、簡単に説明します.
素朴なアルゴリズム
げんり
ほほほ、本当にどこまでも素朴なアルゴリズムがありますね.1つのネットワークストリームについて、私たちはその残量ネットワークの中の拡張路を考慮して、私たちはBFS暴力で探して、それから絶えず拡張して、最後に必ず正しい答えを得ることができて、しかしその効率は非常に低くて、しかもその時間の複雑さは最後の最大ストリームの大きさと関係があって、このようにとても穴があいて、もし私たちが最大ストリームが100000のネットワークを考えるならば、毎回私たちはランダムに拡張路を探しているので、このような状況を構築することができます.このように拡張するには、毎回1単位の流量しか拡張できません.私たちは少なくとも1000000回の拡張が必要で、必ずタイムアウトします.このような書き方はお勧めしません.
コードピット補完
ISAPアルゴリズム
これは私が比較的によく使うアルゴリズムで、その効率はきっと素朴なアルゴリズムよりずっと良くて、最も良いわけではありませんが、しかし大部分のネットの流れの問題にも対処することができます
げんり
実はこのアルゴリズムについて話す前にDinicアルゴリズムをやるべきです.Dinicの改良と言えるからです.しかし、私はDinicを書いたことがありません.原理は知っていますが.ISAPは,拡張後に階層図(Dinicアルゴリズムに対して)を再構築するのではなく,デッドパスが現れるまで拡張路を探し続け,ノードに対してretreat操作を行い,現在デッドパスに入っているノードのd値のみを変更することを考えている.このようにして、私たちは多くの時間を節約することができます(DinicではBFSに相当していますが、もともと多くのリソースの使用空間がありますが、非情に浪費されています).ISAPには効率を向上させる最適化がたくさんありますが、個人的にはISAPアルゴリズムの使用をお勧めします.
ここで、BFSは各ノードから合流点までの最小距離を求めるために用いられ、各アークの長さが1であると仮定するので、BFSを直接走ることができる
拡張するときは、ノードの前のアークに沿って移動するたびに、増分を統計し、再び移動して、この増分を各アークに反映します.
次はコードです
コード#コード#
#include1];
if(!vis[op.u]&&op.cap>op.flow){
vis[op.u]=true;
d[op.u]=d[u]+1;
bfs.push(op.u);
}
}
}
if(!d[s])return false;
return true;
}// BFS
int Augment(){
int u=t,flow=INF;
while(u!=s){
edge op=e[p[u]];
flow=min(flow,op.cap-op.flow);
u=op.u;
}
u=t;
while(u!=s){
e[p[u]].flow+=flow;
e[p[u]^1].flow-=flow;
u=e[p[u]].u;
}
return flow;
}//
int Maxflow(){
int maxflow=0;
if(!BFS())return maxflow;
for(int i=1;i<=n;i++){
num[d[i]]++;// d
}
int u=s;
while(d[s]if(u==t){
maxflow+=Augment();//
u=s;
}
bool if_ope=0;
for(int i=cur[u];i// cur
edge op=e[geo[u][i]];
if(d[op.v]==d[u]-1&&op.cap>op.flow){
p[op.v]=geo[u][i];
cur[u]=i;
if_ope=1;
u=op.v;
break;
}
}
if(!if_ope){// retreat
int m=n-1;
for(int i=0;iif(op.cap>op.flow){
m=min(m,d[op.v]);
}
}// d
num[d[u]]--;
if(num[d[u]]==0)break;//Gap ，
num[m+1]++;
d[u]=m+1;
cur[u]=0;
if(u!=s)u=e[p[u]].u;
}
}
return maxflow;
}
int main(){
/*freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);*/
scanf("%d%d%d%d",&n,&m,&s,&t);
int x,y,z;
for(int i=0;iscanf("%d%d%d",&x,&y,&z);
Add_Edge(x,y,z);
}
printf("%d",Maxflow());
return 0;
} 上のコードの詳細に注意して、それらの多くは注釈でマークされています.また、上のコードが弧を保存するときにvectorを採用しています.効率が悪い場合は、フォワードスターを使用することができます.
もうちょっと...非常に知的障害の詳細は、BFSはstackではなくqueueを使用します.
Dinicアルゴリズム
しばらく書きません
今、私たちは次の問題を研究します.それは..あ、いいえ、もう一つの小さな定理があります.それは最小割最大流の定理です.
さいしょうわりこみさいだいりゅうのていり
この定理は,任意のトラフィックネットワークで求めた最小割合がこのネットワークの最大ストリームに等しいことを意味し,最小割合を解くすべての問題が最大ストリームアルゴリズムを用いて解決できるようにした.
さいしょうわりあてていぎ
最小割合は1つのネットワークを交差しない2つの部分に分けることができる1つのアークの集合であり、私たちはこれらのアークの容量の和をこの割合の容量と呼ぶが、私たちの目的は1つのネットワークの中の1つの容量の最小割合を解くことであり、最小割合と呼ばれ、私たちはこの最小割合の大きさがこのネットワークの最大ストリームに等しいことを証明することができ、複雑ではないことを証明することができる.最小割合定義およびネットワークストリームの性質から証明できる
最小費用最大フローの問題
この問題は比較的実用的な意義を持ち,ネットワークストリーム問題と一般的な図論問題をうまく結びつけた.この問題は、各アークが上記の属性のほかに1つの属性を有する費用付きネットワークに適用される.単位流量の費用は、流量が最大であることを保証する場合に、このネットワーク費用の最小値を求める.
私たちの考えは簡単です.私たちがさっき拡張路を探す方法は相対的に任意なので、その速度が十分に速い限りできますが、この問題では、実行可能な最大ストリームを任意に探すことはできません.新しい制限があり、費用が最も小さいからです.したがって,ネットワークを順次巡回することを考慮することができ,すなわち,費用に関する図を構築し,この図上で最短ルートを走ることによって実現できる.最短のアルゴリズムはSPFAを使うことができて、書くのが便利で走るのが速いです
次はコードです
コード#コード#
//#pragma GCC optimize "O3"
#includeop.flow&&d[op.to]>d[fr]+op.fe){
p[op.to]=geo[fr][i];
d[op.to]=d[fr]+op.fe;
if(!vis[op.to]){
spfa.push(op.to);
vis[op.to]=true;
}
}
}
}
if(d[t]>=INF)return false;
return true;
}*/
bool SPFA(){
spfa.push(t);
memset(vis,0,sizeof(vis));
memset(p,-1,sizeof(p));
for(int i=1;i<=n;i++){
d[i]=INF;
}
d[t]=0;
vis[t]=true;
while(!spfa.empty()){
int fr=spfa.top();
spfa.pop();
vis[fr]=false;
for(int i=0;i1];
if(op.cap>op.flow&&d[op.fr]>d[fr]+op.fe){
p[op.fr]=geo[fr][i]^1;
d[op.fr]=d[fr]+op.fe;
if(!vis[op.fr]){
spfa.push(op.fr);
vis[op.fr]=true;
}
}
}
}
if(d[s]>=INF)return false;
return true;
}
/*void Augment(int& maxflow,int& mincost){
int now=t,flow=INF;
while(now!=s){
edge op=e[p[now]];
flow=min(flow,op.cap-op.flow);
now=op.fr;
}
now=t;
while(now!=s){
int k=p[now];
e[k].flow+=flow;
e[k^1].flow-=flow;
now=e[k].fr;
}
maxflow+=flow;
mincost+=flow*d[t];
}*/
void Augment(int& maxflow,int& mincost){
int now=s,flow=INF;
while(now!=t){
edge op=e[p[now]];
flow=min(flow,op.cap-op.flow);
now=op.to;
}
now=s;
while(now!=t){
int k=p[now];
e[k].flow+=flow;
e[k^1].flow-=flow;
now=e[k].to;
}
maxflow+=flow;
mincost+=flow*d[s];
}
void Mincost_Maxflow(int& maxflow,int& mincost){
while(SPFA()){
Augment(maxflow,mincost);
}
}
void preprocess(){
s=0,t=n+1;
Add_Edge(0,1,2,0);
Add_Edge(n,n+1,2,0);
return;
}
int main(){
/*freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);*/
scanf("%d%d%d%d",&n,&m,&s,&t);
int x,y,z,k;
//preprocess();
for(int i=0;iscanf("%d%d%d%d",&x,&y,&z,&k);
Add_Edge(x,y,z,k);
}
int maxflow=0,mincost=0;
Mincost_Maxflow(maxflow,mincost);
printf("%d %d",maxflow,mincost);
return 0;
} この中の注釈の落ちた部分は逆走の最短路と広がりを採用して、同時に本コードはVectorを採用して、時間の効率の要求が厳格であれば前向星に変えることができます
もういいから前向きな星を貼っておこう
#includeop.flow&&d[op.fr]>d[fr]+op.fe){
p[op.fr]=geo[fr][i]^1;
d[op.fr]=d[fr]+op.fe;
if(!vis[op.fr]){
spfa.push(op.fr);
vis[op.fr]=true;
}
}
}
}
if(d[s]>=INF)return false;
return true;
}*/
void Augment(int& maxflow,int& mincost){
int now=t,flow=INF;
while(now!=s){
edge op=e[p[now]];
flow=min(flow,op.cap-op.flow);
now=e[p[now]^1].to;
}
now=t;
while(now!=s){
int k=p[now];
e[k].flow+=flow;
e[k^1].flow-=flow;
now=e[k^1].to;
}
maxflow+=flow;
mincost+=flow*d[t];
}
/*void Augment(int& maxflow,int& mincost){
int now=s,flow=INF;
while(now!=t){
edge op=e[p[now]];
flow=min(flow,op.cap-op.flow);
now=op.to;
}
now=s;
while(now!=t){
int k=p[now];
e[k].flow+=flow;
e[k^1].flow-=flow;
now=e[k].to;
}
maxflow+=flow;
mincost+=flow*d[s];
}*/
void Mincost_Maxflow(int& maxflow,int& mincost){
while(SPFA()){
Augment(maxflow,mincost);
}
}
void preprocess(){
s=0,t=n+1;
Add_Edge(0,1,2,0);
Add_Edge(n,n+1,2,0);
return;
}
int main(){
/*freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);*/
scanf("%d%d%d%d",&n,&m,&s,&t);
int x,y,z,k;
//preprocess();
for(int i=0;iscanf("%d%d%d%d",&x,&y,&z,&k);
Add_Edge(x,y,z,k);
}
int maxflow=0,mincost=0;
Mincost_Maxflow(maxflow,mincost);
printf("%d %d",maxflow,mincost);
return 0;
} 上のカード定数の最適化を無視してください
ほかにも、いくつかあるかもしれませんが、今日はちょっと疲れたので、先にここまでやりました.