Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 纪念一下终于过了第一条网络流。。 附一个0ms的push-relabel解法

Posted by jskkk123 at 2018-07-17 17:01:08 on Problem 1273
```#include <cstdio>
#include <cstring>

#define _N 500
#define _NL 4096

using namespace std;

int g[_N],h[_N],e[_N],z[_N];
int bp,bq,b[_NL];

struct node{
int y,val,p;
void ini(int a, int b, int c){
y=a;
val=b;
p=c;
}
void show(){
printf("%d %d %d\n",y,val,p);
}
} s[3000];

int n,m;

int main(){

int x,y,val,p,v,w,h_min;
while (scanf("%d%d",&n,&m)>0){
p=2;                             //(We use 0 to mark g[]） 2^1=3, 3^1=2; In this way can we ...
memset(g,0,sizeof(g));
for (int i=1;i<=n;++i){
scanf("%d%d%d",&x,&y,&val);
s[p].ini(y,val,g[x]);
g[x]=p;
++p;
s[p].ini(x,0,g[y]);           //backside
g[y]=p;
++p;
}

memset(h,0,sizeof(h));
memset(e,0,sizeof(e));
memset(z,0,sizeof(z));
p=g[1];
while (p!=0){
e[1]+=s[p].val;
p=s[p].p;
}
h[1]=m;                  // !!
z[1]=1;
bp=0;bq=1;
b[0]=1;

while (bp!=bq){
v=b[bp];
p=g[v];
h_min = _N+_N;
while (e[v]>0 && p!=0){
w=s[p].y;
if (h[v]>h[w]){
if (e[v]<s[p].val){
s[p].val-=e[v];
s[p^1].val+=e[v];
e[w]+=e[v];
e[v]=0;
}else{
e[v]-=s[p].val;
e[w]+=s[p].val;
s[p^1].val+=s[p].val;
s[p].val=0;
}
if (!z[w] && w!=1 && w!=m){               //切记不可加入源点汇点
z[w]=1;
b[bq]=w;
++bq;
if (bq>=_NL) bq=0;
}
}else{
if (h[w]<h_min) h_min = h[w];
}
p=s[p].p;
}
if (e[v]>0 && v!=1){ //非常规做法的一个小坏处
h[v] = h_min+1;                      //MOST important!
b[bq]=v;
++bq;
if (bq>=_NL) bq=0;
}else{
z[v]=0;
}
++bp;
if (bp>=_NL) bp=0;

}

printf("%d\n",e[m]);

}

return 0;
}```

Followed by: