【题目大意】 N个点M条边，每个点的距离标号已给出，且I阶段的点只向I+1阶段的点连边，求最大流。
【算法分析】本来以为是直接sap秒杀。。。因为见惯了这sap的暴力。。。但是做了这题以后，我终于知道了一件事，sap不是万能的，没有sap却是万万不能的。。。
这个比较囧。一开始以为水题，直接sap，10分钟交上去，TLE AT 17
然后就各种囧，加了个优化，就是预处理sap的d数组，依然飘逸地TLE
然后我就是开始想HLPP，但是用不习惯，不爽。。。
然后我就想，能不能把sap和预流推进搞到一起去呢？
于是就诞生了今天我写的这个东东。。。
下面进入正题：
其实说来也简单，因为是层次图，所以我就先从S点开始bfs地向后推进一次，然后在根据上一次bfs的list把上一次推进不能到达T的盈余推回到S来，然后就可以初始了一个流出来
最后再用bfs预处理sap的标号，最后用我们可爱的sap把它解决了。。。
【其它】重写以后1A
994533 02.02.10 17:37 edward 212 .CPP Accepted 1412 ms 15643 kb 这个比较激动。。。看着比较少人A，加上经历了艰难困苦以后终于AC，yeah一个
【CODE】
#include
#define E 666666
//#define N 100
//#define E 200
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,op,c;}g[E];
int n,edge,L,S,T;
int e[N],fa[N],ls[N],cur[N],d[N],num[N],list[N],C[E],v[N];
inline void addedge(int x,int y,int c){
edge++;
g[edge].x=x; g[edge].y=y; g[edge].c=c; g[edge].op=edge+1;
g[edge].next=ls[x]; ls[x]=edge;
edge++;
g[edge].x=y; g[edge].y=x; g[edge].c=0; g[edge].op=edge-1;
g[edge].next=ls[y]; ls[y]=edge;
}
void init(){
int m,x,y,c;
scanf("%d%d%d",&n,&m,&L);
for (int i=1;i<=n;i++){
scanf("%d",&x);
if (x==1) S=i;
if (x==L) T=i;
}
for (int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
C[edge]=c;
C[edge-1]=c;
}
}
void first_push(){
list[1]=S; e[S]=inf; v[S]=1;
int head=0,tail=1,nf;
while (head!=tail){
head++;
for (int t=ls[list[head]];t;t=g[t].next)
if ((t&1) && g[t].c){
nf=g[t].c; if (e[list[head]]
e[g[t].y]+=nf;
g[t].c-=nf;
if (nf && !v[g[t].y]){
tail++;
list[tail]=g[t].y;
v[g[t].y]=1;
}
}
}
// push back
for (int i=tail-1;i>=1;i–){
for (int t=ls[list[i]];t;t=g[t].next)
if (!(t&1) && (C[g[t].op]-g[g[t].op].c)){
nf=C[g[t].op]-g[g[t].op].c; if (e[list[i]]
e[g[t].y]+=nf;
g[g[t].op].c+=nf;
}
}
}
void prebfs(){
for (int i=1;i<=n;i++) d[i]=inf;
list[1]=T; d[T]=0;
int head=0,tail=1;
while (head!=tail){
head++;
for (int t=ls[list[head]];t;t=g[t].next)
if (!(t&1) && g[g[t].op].c && d[g[t].y]==inf){
d[g[t].y]=d[g[t].x]+1;
tail++;
list[tail]=g[t].y;
}
}
}
void relabel(int k){
int mm=n;
cur[k]=ls[k];
for (int t=ls[k];t;t=g[t].next)
if (g[t].c && d[g[t].y]
}
void change(){
int nf=inf;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}
void sap(){
for (int i=1;i<=n;i++){
num[d[i]]++;
cur[i]=ls[i];
}
int i=S;
while (d[S]
if (g[cur[i]].c && d[g[cur[i]].y]+1==d[i]) break;
if (!cur[i]){
num[d[i]]–;
if (num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
change();
i=S;
}
}
}
}
void print(){
for (int i=1;i
}
int main(){
init();
first_push();
prebfs();
sap();
print();
}