MnZn刚学网络瘤,EK算法全部TLE+RE求助
查看原帖
MnZn刚学网络瘤,EK算法全部TLE+RE求助
477258
charleshe楼主2023/2/11 17:17
#include <iostream>
#include <queue>
#define int long long
using namespace std;
struct edge{
	int v,w,nxt;
};
edge e[5005];
int h[202];
int cnt=1;
void add(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=h[u];
	h[u]=cnt;
}
int n,m,s,t;
int lst[202];
int flw[202];
int flg[202][202];
bool bfs(){
	for(int i=1;i<=n;i++) lst[i]=-1;
	queue<int> q;
	q.push(s);
	flw[s]=1ll<<60;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u==t) break;
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(w>0&&lst[v]==-1){
				lst[v]=u;
				flw[v]=min(flw[u],w);
				q.push(v);
			}
		}
	}
	return lst[t]>-1;
}
int EK(){
	int maxf=0;
	while(bfs()){
		maxf+=flw[t];
		for(int i=t;i!=s;i=e[lst[i]^1].v){
//			cout<<e[i].v<<" "<<e[i].w<<" "<<endl;
			e[lst[i]].w-=flw[t];
			e[lst[i]^1].w+=flw[t];
		}
	}
	return maxf;
}
signed main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		if(!flg[u][v]){
			add(u,v,w);
			add(v,u,0);
//			cout<<u<<" "<<v<<" "<<w<<endl;
			flg[u][v]=cnt;
		}
		else e[flg[u][v]-1].w+=w;
	}
//	for(int i=1;i<=n;i++){
//		for(int j=h[i];j;j=e[j].nxt) cout<<i<<" "<<e[i].v<<" "<<e[j].w<<endl;
//	}
	cout<<EK()<<endl;
	return 0;
}

写错了轻喷

差不多是照着这个写的

2023/2/11 17:17
加载中...