91分求助
查看原帖
91分求助
234582
zpl__hhd楼主2021/1/17 19:07

大家来找茬

#include <bits/stdc++.h>
using namespace std;
const int maxn=210,maxm=5010;
int n,m,s,t,cnt=1;//注意cnt=1!!!!!
long long ans;
int head[maxn],cur[maxn],dis[maxn];
struct edge
{
	int t,next;
	long long f;
}e[maxm<<1];
void add(int f,int t,long long w)
{
	e[++cnt].f=w;
	e[cnt].t=t;
	e[cnt].next=head[f];
	head[f]=cnt;
}
bool bfs()
{
	memset(dis,-1,sizeof(dis));
	dis[s]=0;
	cur[s]=head[s];
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int v=e[i].t;
			if(e[i].f&&dis[v]==-1)
			{
				dis[v]=dis[x]+1;
				cur[v]=head[v];
				q.push(v);
			}
		}
	}
	return dis[t]!=-1;
}
long long dinic(int x,long long flow)
{
	if(x==t)return flow;
	long long tmp=flow;
	for(int i=cur[x];i;i=e[i].next)
	{
		cur[x]=i;
		int v=e[i].t;
		if(e[i].f&&dis[v]==dis[x]+1)
		{
			long long d=dinic(v,min(e[i].f,flow));
			if(d==0)dis[v]=INT_MAX;
			e[i].f-=d;
			e[i^1].f+=d;
			tmp-=d;
			if(tmp==0)break;
		}
	}
	return flow-tmp;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,f;
		scanf("%d%d%d",&u,&v,&f);
		add(u,v,f);
		add(v,u,0);
	}
	while(bfs())ans+=dinic(s,INT_MAX);
	printf("%lld",ans);
}  ```
2021/1/17 19:07
加载中...