明天省夏要讲网络流啦！晚上翻出自己的模板发现是蓝书模板QwQ。。拿出以前的提交代码（AC过的？）

曾经的提交记录

 

在luogu上重新提交一遍，结果gg...OVO

没有去除多余的inline

去除了多余的inline

 

论强数据练考验模板的好处？

于是决定自造一份正常的模板。。。

主要的优化有三——

(1) 当前弧优化，防止因重复访问一条边造成效率降低。

(2) 记录无法增广的点。

(3) 玄学优化？在Dinic的bfs过程中找到一条可增广的路径就返回(由于bfs的低效？)，此优化在luogu的数据中表现良好。

具体可以看注释

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 #define inf 0x3f3f3f3f  7   8 int read(){  9     bool flag=0; 10     char ch; 11     int re=0; 12     while((ch=getchar())!='-'&&(ch<'0'||ch>'9')); 13     ch=='-'?flag=1:re=ch-'0'; 14     while((ch=getchar())>='0'&&ch<='9')  re=re*10+ch-'0'; 15     return flag?-re:re; 16 } 17  18 struct edge{ 19     int to,nxt,cap; 20     edge(int to=0,int nxt=0,int cap=0): 21         to(to),nxt(nxt),cap(cap){} 22 }; 23  24 const int maxn=10005,maxm=100005; 25  26 int n,m,s,t,cnt=1; 27 int tou[maxn],head[maxn],q[maxn],d[maxn]; 28 edge edges[maxm<<1]; 29  30 //增加一条流量为c的正向边和流量为0的反向边 31 //利于记录边的流量状态  32 inline void add_edge(int from,int to,int c){ 33     edges[++cnt]=edge(to,head[from],c); 34     head[from]=cnt; 35     edges[++cnt]=edge(from,head[to],0); 36     head[to]=cnt; 37 } 38  39 void init(){ 40     n=read();  m=read();  s=read();  t=read(); 41     for(int i=0,from,to,c;i
        
       
      
     

亲测表现良好。。。