EK+SPFA求调
查看原帖
EK+SPFA求调
571193
ssy1234楼主2023/3/11 20:17
#include<bits/stdc++.h>
#define ll long long
const int MAXN=10000;
const int INF=512475;
using namespace std;
struct edge
{
	int to,w,c,next;
}edges[MAXN*2];
int head[MAXN],cnt=1;
void add(int from,int to,int w,int c)
{
	edges[++cnt].to=to;
	edges[cnt].w=w;
	edges[cnt].next=head[from];
	head[from]=cnt;
}
int n,m,s,t,last[MAXN],flow[MAXN],inq[MAXN],dis[MAXN];
queue<int>q;
bool SPFA()
{
	
	while(!q.empty())
	{
		q.pop();
	}	
	memset(last,-1,sizeof(last));
	memset(inq,0,sizeof(inq));
	memset(dis,127,sizeof(dis));
	flow[s]=INF;
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		inq[p]=0;
		for(int i=head[p];i!=0;i=edges[i].next)
		{
			int to=edges[i].to;
			int vol=edges[i].w;
			if(vol>0&&dis[to]>dis[p]+edges[i].c)
			{
				last[to]=i;
				flow[to]=min(flow[p],vol);
				dis[to]=dis[p]+edges[i].c;
				if(!inq[to])
				{
					q.push(to);
					inq[to]=1;
				}
			}
		}
	}
	return last[t]!=-1;
}
ll maxflow,mincost;
void MCMF()
{
	while(SPFA())
	{
		maxflow+=flow[t];
		mincost+=dis[t]*flow[t];
		int i;//这个地方编译器老是过不了,我就这样干了,为什么?
		for(i=t;i!=s;i=edges[last[i]^1].to);
		{
			edges[last[i]].w-=flow[t];
			edges[last[i]^1].w+=flow[t];
		}
	}
}
int main()
{
	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);
	}
	MCMF();
	printf("%lld %lld",maxflow,mincost);
}

54分其他点有WA和TLE的

2023/3/11 20:17
加载中...