社区讨论

捞,玄关

灌水区参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lzj6tr72
此快照首次捕获于
2024/08/07 09:45
2 年前
此快照最后确认于
2024/08/07 10:32
2 年前
查看原帖
最大流代码求调
CPP
#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,s,t;
struct edge{
	int cap;
	int rec;
	int to;
};
vector<edge> G[250];
int level[250];
int iter[250];
void add(int from,int to,int cap){
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s){
	memset(level,-1,sizeof(level));
	level[s]=0;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(e.cap>0&&level[e.to]<0){
				level[e.to]=level[v]+1;
				q.push(e.to);
			}
		}
	}
}
int dfs(int v,int t,int f){
	if(v==t) return f;
	for(int &i=iter[v];i<G[v].size();i++){
		edge &e=G[v][i];
		if(e.cap>0&&level[v]<level[e.to]){
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rec].cap+=d;
				return d;
			}
		}
	}
}
int dinic(int s,int t){
	int flow=0;
	while(1){
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f=dfs(s,t,INF))>0){
			flow+=f;
		}
	}
}
signed main(){
	cin>>n>>m>>s>>t;
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	cout<<dinic(s,t);
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...