[求助]EK+SPFA , wa了后四个点
查看原帖
[求助]EK+SPFA , wa了后四个点
258071
xiaoyaqing楼主2022/1/16 16:50
#include<bits/stdc++.h>
using namespace std;
int fst[200005],nxt[200005],to[200005],w[200005],ww[200005],idx=1; 
int vis[200005],dis[200005],n,m,s,t,sum=0,ans=0;
const int inf=1e9;
struct node
{
	int e,edge;
}pre[200005];
int read()
{
	int t=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-' ) f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		t=t*10+ch-48;
		ch=getchar();
	}
	return t*f;
}
int add(int a,int b,int c,int d)
{
	++idx;
	nxt[idx]=fst[a];
	fst[a]=idx;
	to[idx]=b;
	w[idx]=c;
	ww[idx]=d;
}
int spfa()
{
	int i,j;
	memset(vis,0,sizeof(vis));
	for(i=1;i<=n;i++) dis[i]=inf;
	queue<int>q;
	q.push(s);
	vis[s]=1;
	dis[s]=0;

	while(!q.empty())
	{
		int x=q.front();
		q.pop(); 
		for(i=fst[x];~i;i=nxt[i])
		{
			int y=to[i],z=ww[i];
			if(w[i]>0&&dis[x]+z<dis[y])
			{
				dis[y]=dis[x]+z;
				pre[y].e=x;
				pre[y].edge=i;
				if(!vis[y]) 
				{
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	return dis[t]!=1e9;
}
void EM()
{
	int i,j,mi=inf;
	
	memset(vis,0,sizeof(vis));
	while(spfa())
	{
		mi=inf;
		for(i=t;i!=s;i=pre[i].e)
			mi=min(mi,w[pre[i].edge]);
		for(i=t;i!=s;i=pre[i].e)
		{
			w[pre[i].edge]-=mi;
			w[pre[i].edge^1]+=mi;
		}
		ans+=mi;
		sum+=mi*dis[t];
	}
}
int main()
{
	int i,j;
	memset(fst,-1,sizeof(fst));
	memset(nxt,-1,sizeof(nxt));
	n=read(),m=read(),s=read(),t=read();
	for(i=1;i<=m;i++)
	{
		int a,b,c,d;
		a=read(),b=read(),c=read(),d=read();
		add(a,b,c,d);
		add(b,a,0,-d); 
	}
	EM();
	printf("%d %d",ans,sum);
	return 0;
}
2022/1/16 16:50
加载中...