请教一下网络最大流这个数据为何能hack这份代码
  • 板块学术版
  • 楼主YONIC
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/5/18 20:57
  • 上次更新2023/10/28 01:10:03
查看原帖
请教一下网络最大流这个数据为何能hack这份代码
536439
YONIC楼主2022/5/18 20:57

data:

6 7 1 6
1 2 1
2 4 1
4 6 1
1 3 1
3 4 1
2 5 1
5 6 1

code:

#include<bits/stdc++.h>
#define int long long
#define M 203
#define M2 (int)(5e3+3)
using namespace std;
int n,m,s,t,now,ans,dep[M<<1],l,r;
queue<int>Q;
bool vis[M];
class graph{
	public:
		int tot,head[M<<1];
		class edge{
			public:
				int nxt,to,w;
		};
		edge h[M2<<1];
		void add(int u,int v,int w){
			h[tot].to=v;
			h[tot].nxt=head[u];
			h[tot].w=w;
			head[u]=tot++;
		}
};
graph G;
bool BFS(){
	memset(dep,0,sizeof(dep));
	Q.push(s);
	dep[s]=1;
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		for(int i=G.head[x];i;i=G.h[i].nxt){
			int y=G.h[i].to;
			if(G.h[i].w&&!dep[y]){ 
				dep[y]=dep[x]+1;
				Q.push(y);
			}
		}
	}
	return dep[t];
}
int DFS(int x,int in){
	if(x==t) return in;
	int out=0;
	for(int i=G.head[x];i&&in;i=G.h[i].nxt){
		int y=G.h[i].to;
		if(G.h[i].w&&dep[y]==dep[x]+1) {
			int res=DFS(y,min(G.h[i].w,in));
			G.h[i].w-=res;
			G.h[i^1].w+=res;
			in-=res;
			out+=res;
		}
	}
	if(!out) dep[x]=0;
	return out;
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for(int i=1,u,v,w;i<=m;++i){
		scanf("%lld%lld%lld",&u,&v,&w);
		G.add(u,v,w);
		G.add(v,u,0);
	}
	while(BFS()) ans+=DFS(s,1e18);
	printf("%lld\n",ans);
	return 0;
}
2022/5/18 20:57
加载中...