ネットワーク・ストリーム:最大ストリーム
4976 ワード
ここ数日ネットの流れを学んで速く血を吐くことを学びます..まず最大ストリームを書き、次の書き込み費用ストリームを書きます.ネットワークフロー定義:うん..基本的にはどの大神が水道管の中の水の流れを見ているのか分からないが、発明した高妙なアルゴリズムは、一つの問題をネットワークの流れモデルに構築し、水流の流れを類比して解決した.(一般的に問題の最適解は、ネットワークストリームの中で最も大きい/小さいストリームに対応する).最大流:パイプの総流量を最大にして、このもののアルゴリズムの中で高い妙なところは逆の辺にあって、绝えず広さを増すことができて复雑度を低くすることができて、具体的なものはネット上で一大をつかんで、打つのがおっくうです..最大フローボード:(dinicアルゴリズム、書きやすい)
#pragma GCC optimize(3)
#include
using namespace std;
const int inf=INT_MAX;
const int N=20010;
int s,t,cnt=-1;
int head[N],next[N*10],to[N*10],las[N*10],deep[N],cur[N];
bool bfs()// ( bfs "bfs "..)
{
int now;queue<int>q;
memset(deep,0,sizeof deep);
deep[s]=1;
q.push(s);
while(!q.empty())
{
now=q.front();q.pop();
for(int i=head[now];i!=-1;i=next[i])
{
if(!deep[to[i]]&&las[i])deep[to[i]]=deep[now]+1,q.push(to[i]);
}
}
return deep[t];
}
int dfs(int pos,int flow)//
{
if(pos==t)return flow;
for(int &i=cur[pos];i!=-1;i=next[i])// , , .
{
if(deep[to[i]]==deep[pos]+1&&las[i])
{
int now=dfs(to[i],min(flow,las[i]));
if(now)
{
las[i]-=now;
las[i^1]+=now;
return now;
}
}
}
return 0;
}
void add_edge(int u,int v,int w)//
{
next[++cnt]=head[u];
las[cnt]=w;to[cnt]=v;
head[u]=cnt;
}
inline void init()
{
memset(next,-1,sizeof next);
memset(head,-1,sizeof head);
return;
}
int main()
{
int n,m,u,v,w,ans=0,tmp;
init();
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=0;iscanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,0);//
}
while(bfs())
{
for(int i=1;i<=n;i++)// cur
cur[i]=head[i];
while(tmp=dfs(s,inf))
ans+=tmp;
}
printf("%d",ans);
return 0;
}