深夜交题,re爆零
查看原帖
深夜交题,re爆零
26837
bjckwrn楼主2020/9/30 01:00

照着白书搞的,定位在add_edge里面push_back有RE,在洛谷IDE里面都能跑,求救

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1000;
const int M=25000;
const int MAX_V=25000;
const ll inf=0x3f3f3f3f;

struct edge{int to;ll cap;int rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,ll cap)
{
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
	return ;
}

void bfs(int s)
{
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty())
	{
		int v=que.front(); que.pop();
		for(int i=0;i<G[v].size();i++)
		{
			edge &e=G[v][i];
			if(e.cap>(ll)0&&level[e.to]<0)
			{
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
	return ;
}

int dfs(int v,int t,ll 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])
		{
			ll d=dfs(e.to,t,min(f,e.cap));
			if(d>0) 
			{
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
}

ll max_flow(int s,int t)
{
	ll flow=0;
	for(;;)
	{
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter,0,sizeof(iter));
		ll f;
		while((f=dfs(s,t,inf))>0) flow+=f; 
	}
}

int main()
{
	
	int x,y,i,j,n,m,S,T;
	ll z;
	scanf("%d %d %d %d",&n,&m,&S,&T);
	for(i=1;i<=n;i++) G[i].clear();
	for(i=1;i<=m;i++)
	{
	scanf("%d %d %lld",&x,&y,&z);
	add_edge(x,y,z);
	}
	ll ans=max_flow(S,T);
	printf("%lld\n",ans);
	
	return 0;
}
2020/9/30 01:00
加载中...