明天的这个时候就在火车上了，所以这是最后一篇了，基本上算是对这次培训的总结。
学术上的东西就不想多说。
但至少我在这次活动中认识不少新朋友，认识到了外面世界的广大，认识到了高人的层出不穷。
我想，回去后，只能说，要抓紧时间，干好每一件要干好的事。
Day5
曹利国带病给我们上课，于是大家甚为感动，学习热情高涨。
“潜伏”了四天的“大牛”们开始踊跃地回答各种问题。
骤然发现，我们这里还有三个要马上去参加冬令营的同学.......
学习了图论的各种算法，发现一个月不做题，思维复杂度下降了。
看来以后要坚持好好学习。
晚自习花了到目前为止的所有时间透彻地研究了最大流的Dinic算法。
打破了我三次学习网络流都失败的悲惨境况（省赛前、同步赛前，NOIP前）
看来RP要回升了（元旦后一直都处于RP低谷中）
于是给模板起名RP_response
声明：这个模板有问题，L的初值应该为1.（在init里面）
RP_response[Ditch 网络最大流模板]
/**//*
USER:zyn19961
LANG:C++
TASK:ditch
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=300;
const int maxm=300000;
const int Inf=0x7fffffff;
struct S
{
int to,next;
int c;
}s[maxm*2];
int level[maxn],Head[maxn],Queue[maxn],out[maxn],L;
int max_flow(int n,int S,int T);
inline void init();
inline void insert(int x,int y,int c);
int m,n;
int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
while(scanf("%ld %ld",&m,&n)!=EOF){
init();
for(int i=0;i<m;i++){
int from,to,cost;
scanf("%ld %ld %ld",&from,&to,&cost);
insert(from,to,cost);
}
int S,T;
S=1;T=n;
printf("%ld\n",max_flow(n,S,T));
}
return 0;
}
inline void init(){
L=0;
memset(Head,0,sizeof(Head));
}
inline void insert(int x,int y,int c){
L++;
s[L].to=y;
s[L].c=c;
s[L].next=Head[x];
Head[x]=L;
L++;
s[L].to=x;
s[L].c=0;
s[L].next=Head[y];
Head[y]=L;
}
int max_flow(int n,int S,int T){
int ret=0;
int head=1,tail=1;
while(1){//while 最多循环N次
//BFS分层 O(M)
for(int i=1;i<=n;i++)
level[i]=0;
head=1,tail=1;
level[S]=1;
Queue[1]=S;
while(head<=tail){
int t=Queue[head];
for(int p=Head[t];p;p=s[p].next)
if(s[p].c&&level[s[p].to]==0){
tail++;
level[s[p].to]=level[t]+1;
Queue[tail]=s[p].to;
}
head++;
}
//
if(level[T]==0)//r如果汇点不在集合中，即不可增广，退出
break;
for(int i=1;i<=n;i++)//枚举从i出发的边
out[i]=Head[i];
int q=0;
while(1){
if(!q){//如果还在源点
int cur;// 前弧
for(cur=out[S];cur;cur=s[cur].next)
//找到下一个节点
if(s[cur].c&&out[s[cur].to]&&level[s[cur].to]==2)
break;
if(cur>0){
q++;
Queue[q]=cur;//用队列存储可增广的路径
out[S]=s[cur].next;
}
else
break;
}
int u=s[Queue[q]].to;
//
if(u==T){//已经走到汇点了,进行增广 最多N次每次 O(N)
int dd=Inf;
int index=0;
for(int i=1;i<=q;i++)//找到最"窄"的边
if(dd>s[Queue[i]].c){
dd=s[Queue[i]].c;
index=i;
}
ret+=dd;//可行流增加
for(int i=1;i<=q;i++){
s[Queue[i]].c-=dd;//正弧减去增加的流量
s[Queue[i]^1].c+=dd;//负弧减去增加的流量
}
for(int i=1;i<=q;i++)
if(s[Queue[i]].c==0){
q=index-1;
break;
//调整到第一个不能增广的弧前的节点，继续寻找增广路，类似回溯
}
}
else{//DFS寻找增广路，配合while，实现非递归！！ O(N*M)
int cur=out[u];
for(;cur;cur=s[cur].next)
if(s[cur].c&&out[s[cur].to]&&level[u]+1==level[s[cur].to])
//找到下一个可行的点
break;
if(cur){//找到了下一个点
q++;
Queue[q]=cur;
out[u]=s[cur].next;
}
else{//回溯
out[u]=0;
q--;
}
}
//
}
}
return ret;
}
曹老师临走前留下了联系方式，想到老师三天里都一直在和我聊天，甚为感动。
若是再不进省队，实在不好和老师联系。