MnZn求助Dinic当前弧优化
查看原帖
MnZn求助Dinic当前弧优化
51569
wgyhm楼主2021/1/5 20:04

这是我没有加当前弧优化的代码,耗时稳定在 100ms 以内:

#include<bits/stdc++.h>
#define maxn 1005
#define rg register
#define int long long
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}//快读
int now[maxn],h[maxn],deep[maxn],head,s,t,n,m;
struct yyy{
	int to,z,w;
	inline void add(int x,int y,int W){
		to=y;z=h[x];h[x]=head;w=W;
	}
}a[100005];
queue<int>q;
inline bool bfs(void){
    rg int i,x;
    memset(deep,0,sizeof(deep));
    q.push(s);deep[s]=1;
    while (!q.empty()){
        x=q.front();q.pop();
        for (i=h[x];i;i=a[i].z)
            if (a[i].w&&!deep[a[i].to]){
                deep[a[i].to]=deep[x]+1;
                q.push(a[i].to);
            }
   }
   return deep[t];
}
inline int dfs(int x,int in){
    rg int i,rest=in,sum;
    if (x==t) return in;
    for (i=h[x];i&&rest;i=a[i].z)
         if (deep[a[i].to]==deep[x]+1&&a[i].w){
             sum=dfs(a[i].to,min(rest,a[i].w));
             if (!sum) deep[a[i].to]=0;
             a[i].w-=sum;a[i^1].w+=sum;rest-=sum;
         }
    return in-rest;
}
inline int Dinic(void){
    int ans=0;
    while (bfs()) ans+=dfs(s,1e9);
    return ans;
}
signed main(){
    rg int i,x,y,z;head=1;
    read(n);read(m);read(s);read(t);
    while (m--){
    	read(x);read(y);read(z);
    	a[++head].add(x,y,z);
    	a[++head].add(y,x,0);
	}
	printf("%lld",Dinic());
	return 0;
}

这是加了当前弧优化,照着《算法竞赛进阶指南》上改的,但是加了以后时间在 900~1000ms 不等。

#include<bits/stdc++.h>
#define maxn 505
#define rg register
#define int long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}//快读
int now[maxn],h[maxn],deep[maxn],head,s,t,n,m;
struct yyy{
	int to,z,w;
	inline void add(int x,int y,int W){
		to=y;z=h[x];h[x]=head;w=W;
	}
}a[100005];
queue<int>q;
inline bool bfs(void){
	memset(deep,0,sizeof(deep));
	rg int i,x;deep[s]=1;q.push(s);
	for (i=1;i<=n;i++) now[i]=h[i];
	while (!q.empty()){
		x=q.front();q.pop();
		for (i=h[x];i;i=a[i].z)
	        if (!deep[a[i].to]&&a[i].w){
	        	deep[a[i].to]=deep[x]+1;
	    	    q.push(a[i].to);
		    }
	}
	return deep[t];
}
inline int dfs(int x,int in){
	if (x==t||!in) return in;
	rg int rest=in,i,sum;
	for (i=now[x];i&&rest;i=a[i].z)
	    if (a[i].w&&deep[a[i].to]==deep[x]+1){
	    	sum=dfs(a[i].to,min(rest,a[i].w));
	    	if (!sum) deep[a[i].to]=0;
	    	a[i].w-=sum;a[i^1].w+=sum;rest-=sum;
		}
    now[x]=a[i].z;//当前弧优化
    return in-rest;
}
inline int Dinic(void){
	rg int ans=0,in;
	while (bfs()) ans+=dfs(s,1e18);
	return ans;
}
signed main(){
    rg int i,x,y,z;head=1;
    read(n);read(m);read(s);read(t);
    while (m--){
    	read(x);read(y);read(z);
    	a[++head].add(x,y,z);
    	a[++head].add(y,x,0);
	}
	printf("%lld",Dinic());
	return 0;
}

请问我的当前弧优化哪里写假了?

还是我加的就是一个假的当前弧优化?

或者说是数据无意就使我的代码这么慢?

调了一个月了,求大佬解答。

2021/1/5 20:04
加载中...