死循环求调
查看原帖
死循环求调
672534
Field_Mouse楼主2023/11/30 22:29

EK+spfa,但是死循环,初步判断是spfa和EK都挂了但调不出来,求

#include<bits/stdc++.h>
#define AC return 0;
#define sc(n) scanf("%d",&(n))
#define pr(n) printf("%lld",(n))
#define hh puts("")
#define kg printf(" ")
#define int long long
using namespace std;
namespace fr{
	int read()
	{
		int x=0,flag=1;
		char ch=getchar();
		for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')flag=-1;
		for(;ch<='9'&&ch>='0';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
		return flag*x;
	}
}
using namespace fr;
struct node{
	int nxt,v,w,c;
}a[50050*2];
int tot=1,cnt;
struct p{
	int l,id;
}rem[50050*2];
int in[50050*2];
int n,m,s,t;
int head[50500*2];
void add(int u,int v,int w,int c)
{
	a[++tot].v=v;
	a[tot].w=w;
	a[tot].nxt=head[u];
	a[tot].c=c;
	head[u]=tot;
}
bool vis[50050];
int dis[50050];
bool spfa()
{
	//pr(++cnt);
	queue <int> q;
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
//	memset(rem,-1,sizeof rem);
	rem[s].id=1<<30;
	while(q.size())
	{
		
		int now=q.front();
		vis[now]=0;
		q.pop();
		for( int i = head[now]; i; i = a[i].nxt)
		{
		//	cout<<a[i].w<<endl;
		//	cout<<i<<endl;
		//	puts("!");
				//	cout<<a[i].c<<endl;
			int to=a[i].v;
			if(dis[to]>dis[now]+a[i].c&&a[i].w)
			{
			//	puts("1");
				dis[to]=dis[now]+a[i].c;
				rem[to].id=min(rem[to].id,a[i].w);
				rem[to].l=i;
			//	cout<<"!"<<to<<" "<<rem[to].l<<endl;
				if(!vis[to])vis[to]=1,q.push(to);
				
			}
		}
	}
	return dis[t]<1e9;
}
int ans,ans1;
void EK()
{
	while(spfa()){
	//	puts("!");	
		ans+=rem[t].id;
		ans1+=dis[t]*rem[t].id;
		for(int i=t;i!=s;i=a[rem[i].l].nxt)
		{
			//cout<<i<<endl;
			a[rem[i].l].w-=rem[t].id;
			a[rem[i].l^1].w+=rem[t].id;
		}
	}
}
signed main()
{
	memset(head,0,sizeof head);
	n=read(),m=read(); s=read(),t=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read(),c=read();
		add(u,v,w,c);
		add(v,u,0,-c);
	//	cout<<"!"<<u<<v<<w<<c<<endl;
	}
	EK();
	pr(ans);kg;pr(ans1);
	AC
}
2023/11/30 22:29
加载中...