求调SPFA
  • 板块学术版
  • 楼主Lazy_Labs
  • 当前回复10
  • 已保存回复10
  • 发布时间2022/2/24 22:41
  • 上次更新2023/10/28 07:48:42
查看原帖
求调SPFA
376137
Lazy_Labs楼主2022/2/24 22:41

RT,费用流,现已知是SPFA(代码中是BFS)出问题了,求调

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define dbout cerr<<"[DeBug]:"
#define mem(x,y) memset(x,y,sizeof(x))
inline int read()
{
 	int x(0),f(1);char c=getchar();
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
	return f*x;
}
const int INF=0x3f3f3f3f,N=5010,M=50010;
int co;
namespace Dinic
{
int head[N],to[M],edge[M],nxt[M],tot,now[M],cost[M];
int n,m,s,t;
int dis[N];
bool vis[N];
void add(int x,int y,int z,int zz,int co)
{
//	cerr<<x<<" "<<y<<" "<<z<<endl;
	to[++tot]=y,edge[tot]=z,cost[tot]=co,nxt[tot]=head[x],head[x]=tot;
	to[++tot]=x,edge[tot]=zz,cost[tot]=-co,nxt[tot]=head[y],head[y]=tot;
}
bool bfs()
{
	cerr<<"BFS"<<endl;
	memset(dis,0x3f,sizeof(dis));
	queue<int>q;
	q.push(s),dis[s]=0,vis[s]=1,now[s]=head[s];
	while(!q.empty())
	{
		int x=q.front();
		q.pop();vis[x]=0;
		for(int i=head[x];i;i=nxt[i])
		{
			int y=to[i];
			if(edge[i]&&dis[y]>dis[x]+cost[i])
			{
				now[y]=head[y];
				dis[y]=dis[x]+cost[i];
				if(!vis[y])q.push(y),vis[y]=1;
			}
		}
	}
	return dis[t]!=INF;
}
int dfs(int x,int f)
{
	cerr<<"DFS"<<endl;
	if(x==t)return f;
	int lft=f,k;
	for(int& i=now[x];i;i=nxt[i])
	if(edge[i]&&dis[to[i]]==dis[x]+cost[i])
	{
		int y=to[i];
		k=dfs(y,min(edge[i],lft));
		if(!k){dis[y]=0;continue;}
		co+=k*cost[i];
		edge[i]-=k;
		edge[i^1]+=k;
		lft-=k;
		if(!lft)return f-lft;
	}
	return f-lft;
}
int dinic()
{
	int ans=0;
	while(bfs())
	ans+=dfs(s,INF);
	return ans;
}
void limit()
{
	n=read();m=read();s=read();t=read();
	tot=1;
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read(),c=read(),d=read();
		add(a,b,c,0,d);
	}
}
}
int main()
{
	fr(P3381_8);
	Dinic::limit();
	int x=Dinic::dinic();
	printf("%d %d",x,co);
	return 0;
}
2022/2/24 22:41
加载中...