dlnic+spfa+slf 全tle了,有没有神仙帮我看看我哪里出问题了
查看原帖
dlnic+spfa+slf 全tle了,有没有神仙帮我看看我哪里出问题了
614984
NNNNzh楼主2022/4/24 21:43
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct e{
	int v,c,f,next;
}edge[100010];
const int inf=0x3f3f3f;
int minfee=0;
int head[100010],dis[100010],vis[100010],cnt;
void add(int u,int v,int w,int c)
{
	edge[++cnt].v=v;
	edge[cnt].c=c;
	edge[cnt].f=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
bool spfa(int u,int v)
{
	memset(vis,0,sizeof(vis));
	memset(dis,inf,sizeof(dis));
	dis[u]=0;
	deque<int>d;
	d.push_back(u);vis[u]=1;
	while(!d.empty())
	{
		int r=d.front();d.pop_front();vis[r]=0;
		for(int i=head[r];i;i=edge[i].next)
		{
			int vi=edge[i].v;
			if(edge[i].f>0&&dis[vi]>dis[r]+edge[i].c)
			{
				dis[vi]=dis[r]+edge[i].c;
				if(!vis[vi])
				{
					if(!d.empty()&&dis[vi]<dis[d.front()])d.push_front(vi);
					else d.push_back(vi);
				}
			}
		}
	}
	return dis[t]!=inf;
}
int dfs(int u,int flow)
{
	if(u==t)return flow;
	int tmp=flow;
	vis[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].v;
		int c=edge[i].c;
		int f=edge[i].f;
		if(f&&!vis[v]&&dis[v]==dis[u]+c)
		{
			int d=dfs(v,min(f,tmp));
			tmp-=d;
			edge[i].f-=d;edge[i^1].f+=d;
			minfee+=d*c;
			if(tmp==0)break;
		}
	}
	vis[u]=0;
	return flow-tmp;
}
void dinic()
{
	int ans=0;
	while(spfa(s,t))
	{
		memset(vis,0,sizeof(vis));
		ans+=dfs(s,inf);
	}printf("%d %d",ans,minfee);
}
int main()
{
	cin>>n>>m>>s>>t;
	int u,v,w,c;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w>>c;
		add(u,v,w,c);
		add(v,u,0,-c);
	}
	dinic();
}
2022/4/24 21:43
加载中...