明天的這個(gè)時(shí)候就在火車上了，所以這是最后一篇了，基本上算是對(duì)這次培訓(xùn)的總結(jié)。
學(xué)術(shù)上的東西就不想多說(shuō)。
但至少我在這次活動(dòng)中認(rèn)識(shí)不少新朋友，認(rèn)識(shí)到了外面世界的廣大，認(rèn)識(shí)到了高人的層出不窮。
我想，回去后，只能說(shuō)，要抓緊時(shí)間，干好每一件要干好的事。
Day5
曹利國(guó)帶病給我們上課，于是大家甚為感動(dòng)，學(xué)習(xí)熱情高漲。
“潛伏”了四天的“大牛”們開(kāi)始踴躍地回答各種問(wèn)題。
驟然發(fā)現(xiàn)，我們這里還有三個(gè)要馬上去參加冬令營(yíng)的同學(xué).......
學(xué)習(xí)了圖論的各種算法，發(fā)現(xiàn)一個(gè)月不做題，思維復(fù)雜度下降了。
看來(lái)以后要堅(jiān)持好好學(xué)習(xí)。
晚自習(xí)花了到目前為止的所有時(shí)間透徹地研究了最大流的Dinic算法。
打破了我三次學(xué)習(xí)網(wǎng)絡(luò)流都失敗的悲慘境況（省賽前、同步賽前，NOIP前）
看來(lái)RP要回升了（元旦后一直都處于RP低谷中）
于是給模板起名RP_response
聲明：這個(gè)模板有問(wèn)題，L的初值應(yīng)該為1.（在init里面）
RP_response[Ditch 網(wǎng)絡(luò)最大流模板]
/**//*
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 最多循環(huán)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如果匯點(diǎn)不在集合中，即不可增廣，退出
break;
for(int i=1;i<=n;i++)//枚舉從i出發(fā)的邊
out[i]=Head[i];
int q=0;
while(1){
if(!q){//如果還在源點(diǎn)
int cur;// 前弧
for(cur=out[S];cur;cur=s[cur].next)
//找到下一個(gè)節(jié)點(diǎn)
if(s[cur].c&&out[s[cur].to]&&level[s[cur].to]==2)
break;
if(cur>0){
q++;
Queue[q]=cur;//用隊(duì)列存儲(chǔ)可增廣的路徑
out[S]=s[cur].next;
}
else
break;
}
int u=s[Queue[q]].to;
//
if(u==T){//已經(jīng)走到匯點(diǎn)了,進(jìn)行增廣 最多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;//負(fù)弧減去增加的流量
}
for(int i=1;i<=q;i++)
if(s[Queue[i]].c==0){
q=index-1;
break;
//調(diào)整到第一個(gè)不能增廣的弧前的節(jié)點(diǎn)，繼續(xù)尋找增廣路，類似回溯
}
}
else{//DFS尋找增廣路，配合while，實(shí)現(xiàn)非遞歸??！ 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])
//找到下一個(gè)可行的點(diǎn)
break;
if(cur){//找到了下一個(gè)點(diǎn)
q++;
Queue[q]=cur;
out[u]=s[cur].next;
}
else{//回溯
out[u]=0;
q--;
}
}
//
}
}
return ret;
}
曹老師臨走前留下了聯(lián)系方式，想到老師三天里都一直在和我聊天，甚為感動(dòng)。
若是再不進(jìn)省隊(duì)，實(shí)在不好和老師聯(lián)系。