您跑的比窝的EK慢诶 /kel
窝还是用cin cout 的
by hater @ 2020-02-08 12:04:05
可能是我蒟蒻自带大常数
by 功在不舍 @ 2020-02-08 12:13:31
我测了三篇题解和我自己的EK 都是在1.6s-1.8s之间啊。。。。这个dinic是1.45s左右
by 功在不舍 @ 2020-02-08 12:18:03
请发题解区
by VinstaG173 @ 2020-02-08 12:18:47
@[hater](/user/100114) 您能发个您的EK代码吗，怎么它那么快
by 功在不舍 @ 2020-02-08 12:20:08
有一说一，Dinic 根本不需要当前弧优化
by hellomath @ 2020-02-08 12:41:27
您跑的比窝dinic慢/kel
by 墨舞灵纯 @ 2020-02-08 12:43:26
```cpp
#include<bits/stdc++.h>
#define Rg register
#define IL inline
#define N 5005
#define M 50005
#define Inf 0x7f7f7f7f
using namespace std ;
int cnt = 1 , n , m , dis[N] , Cost , dep[N] , head[N] , s , t , Ans , incf[N] , pre[N] ;
bool In[N] , vis[N] ; queue <int> q ; int edge[M<<1] , ver[M<<1] , fi[M<<1] ,next[M<<1] ;
void add( int x , int y , int z , int w ) {
ver[++cnt] = y ; edge[cnt] = z ; fi[cnt] = w ;
next[cnt] = head[x] ; head[x] = cnt ;
}
bool bfs( ) {
for(Rg int i=1; i<=n; i++) dis[i] = Inf ;
for(Rg int i=1; i<=n; i++) In[i] = 0 ;
dis[s] = 0 ; q.push(s) ; incf[s] = Inf ;
int x , y , z , act ;
while( !q.empty( ) ) {
x = q.front( ) ; q.pop( ) ; In[x] = 0 ;
for(Rg int i=head[x]; i ; i=next[i]) {
y = ver[i] ; z = fi[i] ; act = edge[i] ;
if( act <= 0 || dis[y] <= dis[x]+z ) continue ;
incf[y] = min( incf[x] , act ) ; pre[y] = i ;
dis[y] = dis[x]+z ;
if( In[y] ) continue ;
In[y] = 1 ; q.push(y) ;
}
} return dis[t] == Inf ? 0 : 1 ;
}
signed main( ) {
Rg int x , y , z , w ;
ios::sync_with_stdio(false) ;
cin.tie(0) ; cout.tie(0) ;
cin >> n >> m >> s >> t ;
for(Rg int i=1; i<=m; i++)
cin >> x >> y >> z >> w ,
add( x , y , z , w ) , add( y , x , 0 , -w ) ;
while( bfs( ) ) {
x = t ; Ans += incf[t] ; Cost += dis[t] * incf[t] ;
while( x != s )
y = pre[x] , edge[y] -= incf[t] ,
edge[y^1] += incf[t] , x = ver[y^1] ;
}
cout << Ans << " " << Cost << endl ;
return 0 ;
}
```
by hater @ 2020-02-08 13:01:25
@[功在不舍](/user/31294) 似乎很正常 queue都是STL的
by hater @ 2020-02-08 13:01:46
@[功在不舍](/user/31294) oh 可能不用memset会快
by hater @ 2020-02-08 13:03:34