EK求助73,没找到实现上的问题
查看原帖
EK求助73,没找到实现上的问题
264548
Tangent233楼主2021/11/26 20:30
#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
const long long inf=1e10+10;
int n,m,s,t;
struct edge
{
	int from,to,cap,flow;
};
vector<edge> edges;
vector<int> g[maxn];
long long a[maxn],p[maxn];
void addedge(int f,int t,int c)
{
	edges.push_back(edge{f,t,c,0});
	edges.push_back(edge{t,f,0,0});
	int m=edges.size();
	g[f].push_back(m-2);
	g[t].push_back(m-1);
}
unsigned int maxflow(int s,int t)
{
	unsigned int flow=0;
	while(1)
	{
		memset(a,0,sizeof(a));
		queue<int> q;
		q.push(s);
		a[s]=inf;
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			for(int i=0;i<g[x].size();i++)
			{
				edge& e=edges[g[x][i]];
				if(!a[e.to]&&e.cap>e.flow)
				{
					p[e.to]=g[x][i];
					a[e.to]=min(a[x],(long long)e.cap-e.flow);
					q.push(e.to);
				}
			}
			if(a[t]) break;
		}
		if(!a[t]) break;
		for(int u=t;u!=s;u=edges[p[u]].from)
		{
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
		}
		flow+=a[t];
	}
	return flow;
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main()
{/*
	freopen("P3376.in","r",stdin);
	freopen("P3376.ans","w",stdout);
*/	n=read(),m=read(),s=read(),t=read();
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		a=read(),b=read(),c=read();
		addedge(a,b,c);
	}
	cout<<maxflow(s,t)<<endl;
	return 0;
}

怎么溢出了 贺了oiwiki的代码

2021/11/26 20:30
加载中...