63pts,EK+SPFA,TLE求调,玄关
查看原帖
63pts,EK+SPFA,TLE求调,玄关
324226
X2H_tato楼主2024/8/9 10:37
#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=1e5+5;
int head[M];
int dis[N],incf[N];
int pre[N],vis[N];
int n,m,s,t;
struct edge{
	int nex,to;
	int w,c;
}e[M];
int cnt=1;
void add (int u,int v,int val,int pa)
{
	e[++cnt].to=v;
	e[cnt].w=val;
	e[cnt].c=pa;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

bool spfa ()
{
	for(int i=1;i<=n;i++) vis[i]=0,dis[i]=2e9;
	queue<int> q;
	incf[s]=2e9;
	vis[s]=1;
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		vis[u]=1;
		q.pop();
		for(int i=head[u];i;i=e[i].nex)
		{
			int v=e[i].to;
			if(e[i].w<=0) continue;
			if(dis[v]>=dis[u]+e[i].c)
			{	
				dis[v]=dis[u]+e[i].c;
				pre[v]=i;
				incf[v]=min(incf[u],e[i].w);
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);					
				}				
			}
		}
	//	cout<<"@";
	}
	if(dis[t]==2e9)
		return 0;
	return 1;
}
long long ans1=0,ans2;
void update ()
{
	int x=t;
	ans1+=incf[t]; 
	ans2+=incf[t]*dis[t];
	while(x!=s)
	{	
		int v=pre[x];	
		e[v].w-=incf[t];
		e[v^1].w+=incf[t];
		x=e[v^1].to;
	}	
} 

int main()
{
	//freopen("a.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,w,c;
		scanf("%d%d%d%d",&u,&v,&w,&c);
		add(u,v,w,c);
		add(v,u,0,-c);
	}
	while(spfa()!=0)
	{
		update();		
	}
	printf("%lld %lld",ans1,ans2);
	return 0;
}

不知道是因为复杂度假了,还是死循环了,还是SPFA四了

2024/8/9 10:37
加载中...