最大ストリームdinicテンプレート
1351 ワード
<span style="font-size:18px;">
//http://blog.csdn.net/u012965890/article/details/38238923
void dinic_bfs(int s)
{
int f,r;
memset(lv,-1,sizeof lv);
q[f=r=0]=s;
lv[s]=0;
while(f<=r)
{
int k=q[f++];
for(int i=fir2[k]; ~i; i=nex2[i])
{
int x=u2[i];
int y=v2[i];
if(cap[i]>flow[i]&&lv[y]<0)
{
lv[y]=lv[x]+1;
q[++r]=y;
}
}
}
}
int dinic_dfs(int s,int t,int f)
{
if(s==t) return f;
for(int &i=iter[s]; ~i; i=nex2[i])
{
int x=u2[i];
int y=v2[i];
if(cap[i]>flow[i]&&lv[s]<lv[y])
{
int d=dinic_dfs(y,t,min(cap[i]-flow[i],f));
if(d>0)
{
flow[i]+=d;
flow[1^i]-=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
memset(flow,0,sizeof flow);
int total=0;
while(1)
{
dinic_bfs(s);
if(lv[t]<0) return total;
memcpy(iter,fir2,sizeof iter);
int f;
while((f=dinic_dfs(s,t,INF))>0)
{
total+=f;
}
}
return total;
}
</span>