[SGU 212]层次图的网络流、预流推进+sap**

【题目大意】 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 #include #include #define N 1555
#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].x]-=nf;
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].x]-=nf;
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]d[k]=mm+1;
}

void change(){
int nf=inf;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].cfor (int i=T;i!=S;i=g[fa[i]].x){
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]for (;cur[i];cur[i]=g[cur[i]].next)
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;iprintf("%dn",C[i]-g[i].c);
}   

int main(){
init();
first_push();
prebfs();
sap();
print();
}   

留下评论

您的电子邮箱地址不会被公开。