问
查看原帖
问
657499
Ayaka_Li楼主2023/8/8 16:52

为什么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;
} 
2023/8/8 16:52
加载中...