想问一下不加弧优化的dinic时间复杂度是多少
查看原帖
想问一下不加弧优化的dinic时间复杂度是多少
324226
X2H_tato楼主2024/8/16 11:35

如果是O(n2m)O(n^2m),那为什么下面代码会T第10个点

#include <bits/stdc++.h>
using namespace std;
const int N=205,M=10005;
const int inf=1<<30;
int dep[N],head[M],vis[N];
int n,m,s,t;
struct edge{
	int nex,to;
	long long w;
}e[M];
int cnt=1;
void add (int u,int v,int val)
{
	e[++cnt].to=v;
	e[cnt].w=val;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

bool bfs ()
{
	for(int i=1;i<=n;i++) dep[i]=1<<30;
	memset(vis,0,sizeof(vis));
	queue<int> q;
	dep[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nex)
		{
			int v=e[i].to;
			if(dep[v]>dep[u]+1&&e[i].w)
			{
				dep[v]=dep[u]+1;
				if(!vis[v])	
				{
					vis[v]=1;
					q.push(v);
				}
			} 
		}
	}
	if(dep[t]==1<<30) 
	{
		return 0;
	}
//	cout<<0x3f<<endl;
	return 1;
}
int cant=0;
long long ans=0;
long long used=0;
long long dfs (int u,long long flow)
{
	long long rflow=0;
	if(u==t) 
	{
		cant=1;
		ans+=flow;
		return flow;
	}
	int used=0;
	for(int i=head[u];i;i=e[i].nex)
	{
		int v=e[i].to;
		if(dep[v]==dep[u]+1&&e[i].w)
		{
			if(rflow=dfs(v,min(flow-used,e[i].w)))
			{
				used+=rflow;
				e[i].w-=rflow;
				e[i^1].w+=rflow;
				if(used==flow) break;
			}
		}
	}
	return used;
}

int main()
{
//	freopen("a.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,0);
	}
	long long tot=0;
	while(bfs())
	{
		cant=1;
		while(cant) 
		{
			cant=0;
			dfs(s,inf);
		}
	}
	cout<<ans;
	return 0;
}

2024/8/16 11:35
加载中...