我的模板 最大流（Dinic & Isap）+最小费用最大流（SPFAFlow）==有更改

今天刻意用poj 3469 http://poj.org/problem?id=3469测了下模板，Isap并不像想象中那么快，难道是我写搓了，而且在网络流与线性规划中的最后一题，isap完败给Dinic了,我的Isap啊~~~不知道那些几百毫秒出解的是用什么算法。。。难道是。。。

   dinic总体上挺不错的，递归版的Isap基本上与Dinic没差别，而非递归版在某些情况反而不如递归版，于是以后一般用Dinic，是在不行用非递归的isap试试

所以比赛中就带1,3两个模板好了

费用流居然忘加了，今天把它加上了= =，在最后。。。

模板1（Dinic递归版 3438MS）：

#include<cstdio>

using namespace std;

const int mm=1000000;

const int mn=22222;

const int oo=1000000000;

int node,src,dest,edge;

int reach[mm],flow[mm],next[mm];

int head[mn],work[mn],dis[mn],q[mn];

inline int min(int a,int b)

{

return a<b?a:b;

}

inline void prepare(int _node,int _src,int _dest)

{

node=_node,src=_src,dest=_dest;

for(int i=0;i<node;++i)head[i]=-1;

edge=0;

}

inline void addedge(int u,int v,int c1,int c2)

{

reach[edge]=v,flow[edge]=c1,next[edge]=head[u],head[u]=edge++;

reach[edge]=u,flow[edge]=c2,next[edge]=head[v],head[v]=edge++;

}

bool Dinic_bfs()

{

int i,u,v,l,r=0;

for(i=0;i<node;++i)dis[i]=-1;

dis[q[r++]=src]=0;

for(l=0;l<r;++l)

for(i=head[u=q[l]];i>=0;i=next[i])

if(flow[i]&&dis[v=reach[i]]<0)

{

dis[q[r++]=v]=dis[u]+1;

if(v==dest)return 1;

}

return 0;

}

int Dinic_dfs(int u,int exp)

{

if(u==dest)return exp;

for(int &i=work[u],v,tmp;i>=0;i=next[i])

if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)

{

flow[i]-=tmp;