2011.07.21
うーん...眠くないから、いっそいろんな流れをやろう~どうせ明日も早起きして実験室に行きたくないんだから...
POJ 1273
題意:赤果果の最大流、n個の点mの辺、1からnの最大流を求めて、題解は下の型版を参照してください.
最大ストリームアルゴリズム:
最大ストリームアルゴリズムは2つの大きなクラスに分けられ、一般的には拡張路(Augmenting Path)と圧入と再符号(Push Relabel)に基づいており、ISAP(以下を参照)のような2つのクラスを結合している点もある.
まず増広路アルゴリズムについて話しましょう~すべての増広路の元祖はFord-Fulkerson法で、具体的には増広可能な道を見つけて見つからないまで増広しますが、これは主に一つの思想として考えられています.ネットワークGにおけるエッジ(i,j)への容量がc(i,j),現在のトラフィックがf(i,j)であると仮定すると,このエッジの残流量はr(i,j)=c(i,j)−f(i,j)であり,その逆エッジの残流量はr(j,i)=f(i,j)である.ネットワーク内の全ての残流量r(i,j)>0の辺に残量ネットワークGfが構成され、拡張経路pは、残量ネットワークにおけるソース点sから終点tまでの経路である.経路pに沿って流量fを拡張する動作は基本的に同じであり,各アルゴリズムの違いは拡張経路pを探す方法が異なることである.例えば、sからtまでの最短経路、または流量が最大の経路を探すことができる.
増広路は最大流の最小割定理と天然で美しいつながりを持っている.最大ストリーム最小分割の定理として,1つのストリームネットワークの頂点セットを2つの集合SとTに分割し,ソース点s∈Sかつ集点t∈T,分割(S,T)の容量C(S,T)=ΣCuv,ここでu∈Sかつv∈Tとする.直感的に見ると,ダイバーシティ(S,T)はソース点sから合流点tまでの必須の道であり,この道が塞がればsからtに流れることができない.そこで,任意のストリームネットワークの最大トラフィックがネットワークの最小割合の容量に等しいという定理を得ることができる.アテステーション:http://bbs.lzjtu.edu.cn/bbsanc.php?path=%2Fgroups%2Fsci.faq%2FComputer%2FProgramOld%2FAlgorithm%2F4%2F5%2F26.txt
この定理に基づくEdmonds‐Karpは応用の一つである.E-Kの考え方はBFSを利用して最短経路の広がりを毎回探し,経路によって広がりを増すことである.複雑度はO(VE 2)であり,実際の応用は少ないが,我々にさらなる構想を提供した.
EK:最短ルート、基本的な増光路アルゴリズムを広く探します.
同じSAP系に属するDinicは効率の高いアルゴリズムであり,BFSとDFSの優位性を結合し,時間的複雑度はO{V^2*E}である.
Dinicアルゴリズムの基本手順は次のとおりです.
1)残存ネットワークの階層図を計算する.我々は、h[i]を頂点iがソースSから通過する最小辺数として定義し、すべての頂点のh値を求め、h[]値が同じ頂点は同じ層に属し、これがネットワークの階層図である.
2)拡張経路が存在しないまで階層図上でBFS拡張を行う.このとき求めた広がり経路上の頂点は階層化されており,経路上に同じ層に属する2つの頂点,すなわちh[i]==h[j](i!=j)が存在するはずがない.同時に,階層図を求めた後,階層図上で複数回拡張することができる.
3)1と2を繰り返す.拡張パスが存在しないまで.
Dinicアルゴリズムが見つけた拡張経路は最も短く,すなわち通過する頂点数が最も少ないことが分かった.さらに、Dinicアルゴリズムは、拡張パスツリーのような複数の拡張パスを同時に見つけることができます(この点は非常に重要です).例えば、私たちは1本の拡張経路を見つけて、この拡張経路の増加した流量はCで、この拡張経路の上で必然的に1本の辺の残留容量はCで、これは私たちがまた起点から拡張路を探す必要がなくて、i頂点から拡張路を探して、このように繰り返し計算を減らして、効率を高めて、これは私たちがまた多重拡張路を探すことです.
Dinic+隣接テーブルテンプレート
Dinic+隣接行列(by DD_engi)
ISAP:
ISAP(improved SAP)は、上述したように、Dinicアルゴリズムとは異なり、各頂点が終点tに到達する距離であるプリプッシュクラスの特徴を導入する.同様に、各頂点の距離ラベルを保存すれば、階層ネットワークを明示的に構築する必要はありません.プログラム開始時にすべての頂点の距離ラベルを1つの逆BFSで初期化し、その後ソースポイントから次の3つの操作を行います.
(1)現在の頂点iが終点である場合の広がり
(2)現在の頂点にdist[i]=dist[j]+1を満たす円弧がある場合に進む
(3)現在の頂点に条件を満たす円弧がない場合は再符号を付けて一歩後退する.全サイクルは、ソース点sの距離ラベルdist[s]>=nで終了する.i点に対する再符号化動作は、dist[i]=1+min{dist[j]:(i,j)残量ネットワークGf}に属すると概括することができる.
中の1つのすごい最適化はGAPである:sからtまでの最短経路の頂点距離符号が単調に減少し、隣接する頂点符号差が厳密に1に等しいため、現在のネットワークにおいて距離符号k(0<=kISAP+GAP+BFS+デュアルチェーンテーブル
そしてこの商品はISAPを自称して、100行の学友の情をどうして堪えることができますか......明日研究してみます:私は本当にISAPが31行のORZを書くことができることを信じません......
証明書:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited
ここではいくつかのSAP類アルゴリズムの効率比較を行い、非常に優秀である.http://dantvt.is-programmer.com/tag/Dinic
また非SAPクラスの最高符号プリフロー推進HLPPは、より速い最大フローアルゴリズムと称されていますので、明日見てみましょう.
http://hi.baidu.com/%B2%DD%B4%CC%E2%AC_sp/blog/item/0a6529b7a7f66dc436d3cae3.html
POJ 1273
題意:赤果果の最大流、n個の点mの辺、1からnの最大流を求めて、題解は下の型版を参照してください.
最大ストリームアルゴリズム:
最大ストリームアルゴリズムは2つの大きなクラスに分けられ、一般的には拡張路(Augmenting Path)と圧入と再符号(Push Relabel)に基づいており、ISAP(以下を参照)のような2つのクラスを結合している点もある.
まず増広路アルゴリズムについて話しましょう~すべての増広路の元祖はFord-Fulkerson法で、具体的には増広可能な道を見つけて見つからないまで増広しますが、これは主に一つの思想として考えられています.ネットワークGにおけるエッジ(i,j)への容量がc(i,j),現在のトラフィックがf(i,j)であると仮定すると,このエッジの残流量はr(i,j)=c(i,j)−f(i,j)であり,その逆エッジの残流量はr(j,i)=f(i,j)である.ネットワーク内の全ての残流量r(i,j)>0の辺に残量ネットワークGfが構成され、拡張経路pは、残量ネットワークにおけるソース点sから終点tまでの経路である.経路pに沿って流量fを拡張する動作は基本的に同じであり,各アルゴリズムの違いは拡張経路pを探す方法が異なることである.例えば、sからtまでの最短経路、または流量が最大の経路を探すことができる.
増広路は最大流の最小割定理と天然で美しいつながりを持っている.最大ストリーム最小分割の定理として,1つのストリームネットワークの頂点セットを2つの集合SとTに分割し,ソース点s∈Sかつ集点t∈T,分割(S,T)の容量C(S,T)=ΣCuv,ここでu∈Sかつv∈Tとする.直感的に見ると,ダイバーシティ(S,T)はソース点sから合流点tまでの必須の道であり,この道が塞がればsからtに流れることができない.そこで,任意のストリームネットワークの最大トラフィックがネットワークの最小割合の容量に等しいという定理を得ることができる.アテステーション:http://bbs.lzjtu.edu.cn/bbsanc.php?path=%2Fgroups%2Fsci.faq%2FComputer%2FProgramOld%2FAlgorithm%2F4%2F5%2F26.txt
この定理に基づくEdmonds‐Karpは応用の一つである.E-Kの考え方はBFSを利用して最短経路の広がりを毎回探し,経路によって広がりを増すことである.複雑度はO(VE 2)であり,実際の応用は少ないが,我々にさらなる構想を提供した.
EK:最短ルート、基本的な増光路アルゴリズムを広く探します.
#include
#include
using namespace std;
const int INF=1000000000;
const int MAX=300;
queueq;
int cap[MAX][MAX]; //
int flow[MAX][MAX]; //
int a[MAX]; //a[i]=j: s i j
int p[MAX]; //p[v]=u:v u
int N,M; //N: M:
int f; //
// s->t
void Edmonds_Karp(int s,int t)
{
int u,v;
memset(flow,0,sizeof(flow));
f=0;
while (true)
{
memset(a,0,sizeof(a));
a[s]=INF;
q.push(s);
while (!q.empty()) //Bfs
{
u=q.front();
q.pop();
for ( v=1;v<=M;v++)
{
if (!a[v] && cap[u][v]>flow[u][v]) // v
{
p[v]=u; // v
q.push(v);
(a[u] < cap[u][v]-flow[u][v]) ? a[v]=a[u] : a[v]=cap[u][v]-flow[u][v]; //s->v
}
}
}
if (a[t] == 0) // ，
{
break;
}
//
for (u=t;u!=s;u=p[u])
{
flow[p[u]][u]+=a[t];
flow[u][p[u]]-=a[t];
}
f+=a[t]; // s
}
printf("%d
",f);
}
int main()
{
int i,j;
int x,y,w;
while (scanf("%d%d",&N,&M) != EOF)
{
memset(cap,0,sizeof(cap));
for (i=1;i<=N;i++)
{
scanf("%d%d%d",&x,&y,&w);
cap[x][y]+=w; //
}
Edmonds_Karp(1,M);
}
return 0;
} 同じSAP系に属するDinicは効率の高いアルゴリズムであり,BFSとDFSの優位性を結合し,時間的複雑度はO{V^2*E}である.
Dinicアルゴリズムの基本手順は次のとおりです.
1)残存ネットワークの階層図を計算する.我々は、h[i]を頂点iがソースSから通過する最小辺数として定義し、すべての頂点のh値を求め、h[]値が同じ頂点は同じ層に属し、これがネットワークの階層図である.
2)拡張経路が存在しないまで階層図上でBFS拡張を行う.このとき求めた広がり経路上の頂点は階層化されており,経路上に同じ層に属する2つの頂点,すなわちh[i]==h[j](i!=j)が存在するはずがない.同時に,階層図を求めた後,階層図上で複数回拡張することができる.
3)1と2を繰り返す.拡張パスが存在しないまで.
Dinicアルゴリズムが見つけた拡張経路は最も短く,すなわち通過する頂点数が最も少ないことが分かった.さらに、Dinicアルゴリズムは、拡張パスツリーのような複数の拡張パスを同時に見つけることができます(この点は非常に重要です).例えば、私たちは1本の拡張経路を見つけて、この拡張経路の増加した流量はCで、この拡張経路の上で必然的に1本の辺の残留容量はCで、これは私たちがまた起点から拡張路を探す必要がなくて、i頂点から拡張路を探して、このように繰り返し計算を減らして、効率を高めて、これは私たちがまた多重拡張路を探すことです.
Dinic+隣接テーブルテンプレート
#include
#include
using namespace std;
const long maxn=300;
const long maxm=300000;
const long inf=0x7fffffff;
struct node
{
long v,next;
long val;
}s[maxm*2];
long level[maxn],p[maxn],que[maxn],out[maxn],ind;
void init()
{
ind=0;
memset(p,-1,sizeof(p));
}
inline void insert(long x,long y,long z)
{
s[ind].v=y;
s[ind].val=z;
s[ind].next=p[x];
p[x]=ind++;
s[ind].v=x;
s[ind].val=0;
s[ind].next=p[y];
p[y]=ind++;
}
long max_flow(long n,long source,long sink)
{
long ret=0;
long h=0,r=0;
while(1){
long i;
for(i=0;i=0){
que[++q]=cur;
out[source]=s[cur].next;
}
else
break;
}
long u=s[que[q]].v;
if(u==sink){
long dd=inf;
long index=-1;
for(i=0;i<=q;i++){
if(dd>s[que[i]].val){
dd=s[que[i]].val;
index=i;
}
}
ret+=dd;
for(i=0;i<=q;i++){
s[que[i]].val-=dd;
s[que[i]^1].val+=dd;
}
for(i=0;i<=q;i++){
if(s[que[i]].val==0){
q=index-1;
break;
}
}
}
else{
long cur=out[u];
for(;cur!=-1;cur=s[cur].next){
if(s[cur].val&&out[s[cur].v]!=-1&&level[u]+1==level[s[cur].v])
break;
}
if(cur!=-1){
que[++q]=cur;
out[u]=s[cur].next;
}
else{
out[u]=-1;
q--;
}
}
}
}
return ret;
}
long m,n;
int main()
{
while(scanf("%ld %ld",&m,&n)!=EOF){
init();
for(int i=0;i Dinic+隣接行列(by DD_engi)
void Dinic()
{
for(;;){
BFS();
if(D[T]==-1)break;
int path_n=0;
int x=S;
memcpy(cur,E,sizeof(cur));
for(;;){
if(x==T){
int mink=-1,delta=INT_MAX;
for(int i=0;icc;
mink=i;
}
}
for(int i=0;ic-=delta;
path[i]->back->c+=delta;
}
path_n=mink;
x=path[path_n]->x;
}
edge* e;
for(e=cur[x];e;e=e->next){
if(e->c==0)
continue;
int y=e->y;
if(D[x]+1==D[y])
break;
}
cur[x]=e;
if(e){
path[path_n++]=e;
x=e->y;
}
else{
if(path_n==0)
break;
D[x]=-1;
--path_n;
x=path[path_n]->x;
}
}
}
} ISAP:
ISAP(improved SAP)は、上述したように、Dinicアルゴリズムとは異なり、各頂点が終点tに到達する距離であるプリプッシュクラスの特徴を導入する.同様に、各頂点の距離ラベルを保存すれば、階層ネットワークを明示的に構築する必要はありません.プログラム開始時にすべての頂点の距離ラベルを1つの逆BFSで初期化し、その後ソースポイントから次の3つの操作を行います.
(1)現在の頂点iが終点である場合の広がり
(2)現在の頂点にdist[i]=dist[j]+1を満たす円弧がある場合に進む
(3)現在の頂点に条件を満たす円弧がない場合は再符号を付けて一歩後退する.全サイクルは、ソース点sの距離ラベルdist[s]>=nで終了する.i点に対する再符号化動作は、dist[i]=1+min{dist[j]:(i,j)残量ネットワークGf}に属すると概括することができる.
中の1つのすごい最適化はGAPである:sからtまでの最短経路の頂点距離符号が単調に減少し、隣接する頂点符号差が厳密に1に等しいため、現在のネットワークにおいて距離符号k(0<=k
#include
#include
using namespace std;
const int maxnode = 1024;
const int infinity = 2100000000;
struct edge{
int ver; // vertex
int cap; // capacity
int flow; // current flow in this arc
edge *next; // next arc
edge *rev; // reverse arc
edge(){}
edge(int Vertex, int Capacity, edge *Next)
:ver(Vertex), cap(Capacity), flow(0), next(Next), rev((edge*)NULL){}
void* operator new(size_t, void *p){
return p;
}
}*Net[maxnode];
int dist[maxnode]= {0}, numbs[maxnode] = {0}, src, des, n;
void rev_BFS(){
int Q[maxnode], head = 0, tail = 0;
for(int i=1; i<=n; ++i){
dist[i] = maxnode;
numbs[i] = 0;
}
Q[tail++] = des;
dist[des] = 0;
numbs[0] = 1;
while(head != tail){
int v = Q[head++];
for(edge *e = Net[v]; e; e = e->next){
if(e->rev->cap == 0 || dist[e->ver] < maxnode)continue;
dist[e->ver] = dist[v] + 1;
++numbs[dist[e->ver]];
Q[tail++] = e->ver;
}
}
}
int maxflow(){
int u, totalflow = 0;
edge *CurEdge[maxnode], *revpath[maxnode];
for(int i=1; i<=n; ++i)CurEdge[i] = Net[i];
u = src;
while(dist[src] < n){
if(u == des){ // find an augmenting path
int augflow = infinity;
for(int i = src; i != des; i = CurEdge[i]->ver)
augflow = min(augflow, CurEdge[i]->cap);
for(int i = src; i != des; i = CurEdge[i]->ver){
CurEdge[i]->cap -= augflow;
CurEdge[i]->rev->cap += augflow;
CurEdge[i]->flow += augflow;
CurEdge[i]->rev->flow -= augflow;
}
totalflow += augflow;
u = src;
}
edge *e;
for(e = CurEdge[u]; e; e = e->next)
if(e->cap > 0 && dist[u] == dist[e->ver] + 1)break;
if(e){ // find an admissible arc, then Advance
CurEdge[u] = e;
revpath[e->ver] = e->rev;
u = e->ver;
} else { // no admissible arc, then relabel this vertex
if(0 == (--numbs[dist[u]]))break; // GAP cut, Important!
CurEdge[u] = Net[u];
int mindist = n;
for(edge *te = Net[u]; te; te = te->next)
if(te->cap > 0)mindist = min(mindist, dist[te->ver]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != src)
u = revpath[u]->ver; // Backtrack
}
}
return totalflow;
}
int main(){
int m, u, v, w;
freopen("ditch.in", "r", stdin);
freopen("ditch.out", "w", stdout);
while(scanf("%d%d", &m, &n) != EOF){ // POJ 1273 need this while loop
memset(dist,0,sizeof(dist));
memset(numbs,0,sizeof(numbs));
memset(Net,0,sizeof(Net));
edge *buffer = new edge[2*m];
edge *data = buffer;
src = 1; des = n;
while(m--){
scanf("%d%d%d", &u, &v, &w);
Net[u] = new((void*) data++) edge(v, w, Net[u]);
Net[v] = new((void*) data++) edge(u, 0, Net[v]);
Net[u]->rev = Net[v];
Net[v]->rev = Net[u];
}
rev_BFS();
printf("%d
", maxflow());
delete [] buffer;
}
return 0;
} そしてこの商品はISAPを自称して、100行の学友の情をどうして堪えることができますか......明日研究してみます:私は本当にISAPが31行のORZを書くことができることを信じません......
#include
#include
#define MAXN 20002
int g[MAXN][MAXN];//,c[MAXN][MAXN],f[MAXN][MAXN];
int m,n;
int vd[MAXN],d[MAXN];
inline min(int a,int b){return a 0 && d[u] == d[v] + 1) //
{
tmp = dfs(v,min(flow-ret,g[u][v])); // ，
g[u][v] -= tmp;
g[v][u] += tmp;
ret += tmp;
if(ret == flow)return ret;
}
if(d[1] >= n) return ret; // n, ,
vd[d[u]]--;
if(vd[d[u]] == 0)d[1] = n; // ,
d[u]++;
vd[d[u]]++;
return ret;
}
int main()
{
int i,x,y,z,flow,ans = 0;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
g[x][y] += z;
//c[x][y] += z;
}
vd[0] = n;
while(d[1] < n)
{
flow = dfs(1,INT_MAX);
ans += flow;
}
printf("max flow=%d
",ans);
return 0;
} 証明書:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited
ここではいくつかのSAP類アルゴリズムの効率比較を行い、非常に優秀である.http://dantvt.is-programmer.com/tag/Dinic
また非SAPクラスの最高符号プリフロー推進HLPPは、より速い最大フローアルゴリズムと称されていますので、明日見てみましょう.
http://hi.baidu.com/%B2%DD%B4%CC%E2%AC_sp/blog/item/0a6529b7a7f66dc436d3cae3.html