关于网络最大流
查看原帖
关于网络最大流
241817
Chancylaser楼主2021/7/21 18:04
#include<iostream>//网络最大流 
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const long long maxn=5005;
long long n,m;
long long s,t;
long long a,b,c;
struct edge{
	long long e,f;
	long long next;
	long long op;
}ed[maxn<<1];
long long first[maxn];
long long en;
void add(long long s,long long e,long long f){
	en++;
	ed[en].next=first[s];
	first[s]=en;
	ed[en].e=e;
	ed[en].f=f;
	en++;
	ed[en].next=first[e];
	first[e]=en;
	ed[en].e=s;
	ed[en].f=0;
	ed[en].op=en-1;
	ed[en-1].op=en;
	return; 
}
long long depth[100005];
long long dfs(long long now,long long flow){
	if(now==t) return flow;
	long long ans=0;
	for(register int i=first[now];i!=0;i=ed[i].next){
		long long e=ed[i].e, f=ed[i].f , op=ed[i].op;
		if(f!=0&&flow!=0&&depth[e]>depth[now]){
			long long delta=dfs(e,min(f,flow));
			ed[i].f-=delta;
			ed[op].f+=delta;
			flow-=delta;
			ans+=delta;
		}
	}
	return ans;
}
bool bfs(long long s){
	queue<long long> q;
	q.push(s);
	memset(depth,0,sizeof(depth));
	depth[s]=1;
	while(q.size()){
		long long now=q.front();
		q.pop();
		for(register int i=first[now];i!=0;i=ed[i].next){
			long long e=ed[i].e , f=ed[i].f;
			if(depth[e]==0&&f!=0){
				depth[e]=depth[now]+1;
				q.push(e);
			}
		}
	}
	return depth[t]!=0;
}
long long dinic(){
	long long ans=0;
	while(bfs(s))
		ans+=dfs(s,1e12+19);
	return ans;
}
int main(){
	//freopen("qwq.txt","r",stdin);
	cin>>n>>m>>s>>t;
	for(register int i=1;i<=m;i++){
		cin>>a>>b>>c;
		add(a,b,c);
	}
	cout<<dinic();
	return 0;
} 

这是我的代码,有一个点tle了,2天了,还没有调出来,有没有神仙给我看一下呀?

2021/7/21 18:04
加载中...