Ayaka_Li @ 2023-08-08 16:52:55
为什么ISAP不跑bfs也能AC a
#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
const int INF=0x7fffffff;
const int N=1e6+10;
struct edge {
int v,nxt,val;
}e[N];
int head[N],cnt=1;//!!!!!!!
inline void add(int u,int v,int w) {
e[++cnt].v=v;
e[cnt].val=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int n,m,s,t;
int dep[N],gap[N];
int M_flow;
int dfs(int u,int flow) {
if (u==t) {
M_flow+=flow;
return flow;
}
int used=0;
for (int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if (e[i].val&&dep[v]+1==dep[u]) {
int mi=dfs(v,min(e[i].val,flow-used));
if (mi) {
e[i].val-=mi;
e[i^1].val+=mi;
used+=mi;
}
if (used==flow)
return used;
}
}
gap[dep[u]]--;
if (gap[dep[u]]==0) dep[s]=n+1;
dep[u]++;
gap[dep[u]]++;
return used;
}
int ISAP() {
M_flow=0;
while (dep[s]<n) {
dfs(s,INF);
}
return M_flow;
}
signed main() {
cin>>n>>m>>s>>t;
while (m--) {
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,0);
}
cout<<ISAP()<<endl;;
return 0;
}
by reveal @ 2023-08-08 20:53:10
ISAP 的 bfs 用于标定初始高度,其满足分层图存在流量。
但是 ISAP 并不要求这点,标定初始高度仅用于减小常数。
by Ayaka_Li @ 2023-08-10 07:07:54
@reveal thx