为什么这道题的ISAP比Dinic还要慢?
查看原帖
为什么这道题的ISAP比Dinic还要慢?
86624
洛谷Onlinejudge楼主2020/8/19 23:32

为什么这道题的ISAP比Dinic还要慢?

是我写的太渣了吗?

#include "bits/stdc++.h"
using namespace std;
#define MAXM 1010000
#define MAXN 501000

struct EDGE{
	int Next,To,Val;
}E[MAXM];
int Head[MAXN],Size=1,Cur[MAXN];
inline void Add(int From,int To,int Val){
	E[++Size].Next=Head[From];
	E[Size].Val=Val;
	Head[From]=Size;
	E[Size].To=To;
	return;
}

int Dep[MAXN],S,T,N,M,Gap[MAXN];
inline void BFS(void){
	for(register int i=1;i<=N;i++)
		Dep[i]=-1,Gap[i]=0;
	Dep[T]=0,Gap[0]=1;
	queue <int> Queue;
	Queue.push(T);
	while(!Queue.empty()){
		int This=Queue.front();
		Queue.pop();
		for(register int i=Head[This];i;i=E[i].Next){
			int To=E[i].To;
			if(Dep[To]>=0)
				continue;
			Queue.push(To);
			Dep[To]=Dep[This]+1;
			Gap[Dep[To]]++;
		}
	}
	return;
}

int Sum=0;
inline int DFS(int This,int Flow){
	if(This==T){
		Sum+=Flow;
		return Flow;
	}
	int Rlow=0,Used=0;
	for(register int i=Cur[This];i;i=E[i].Next){
		int To=E[i].To;Cur[This]=i;
		if(E[i].Val<=0||Dep[This]!=(Dep[To]+1))
			continue;
		Rlow=DFS(To,min(Flow-Used,E[i].Val));
		if(Rlow==0)continue;
		Used+=Rlow;
		E[i^1].Val=E[i^1].Val+Rlow;
		E[i].Val=E[i].Val-Rlow;
		if(Used==Flow)return Used;
	}
	Gap[Dep[This]]--;
	if(Gap[Dep[This]]==0)
		Dep[S]=N+1;
	Dep[This]++;
	Gap[Dep[This]]++;
	return Used;
}

#define INF 1<<28
inline void ISAP(void){
	BFS();
	while(Dep[S]<N){
		for(register int i=1;i<=N;i++)
			Cur[i]=Head[i];
		DFS(S,INF);
	}
	return;
}

int N1,N2,N3,M1,M2,X,Y;
int main(void){
	scanf("%d%d%d%d",&N1,&N2,&N3,&M1);
	N=N1+N1+N2+N3+2;
	S=N1+N1+N2+N3+1;
	T=N1+N1+N2+N3+2;
	for(register int i=1;i<=N2;i++){
		Add(S,i,1);
		Add(i,S,0);
	}
	for(register int i=1;i<=M1;i++){
		scanf("%d%d",&X,&Y);
		Add(Y,X+N2,1);
		Add(X+N2,Y,0);
	}
	for(register int i=1;i<=N1;i++){
		Add(N2+i,N1+N2+i,1);
		Add(N1+N2+i,N2+i,0);
	}
	scanf("%d",&M2);
	for(register int i=1;i<=M2;i++){
		scanf("%d%d",&X,&Y);
		Add(X+N1+N2,Y+N1+N1+N2,1);
		Add(Y+N1+N1+N2,X+N1+N2,0);
	}
	for(register int i=(N1+N2+N1+1);i<(N-1);i++){
		Add(i,T,1);
		Add(T,i,0);
	}
	ISAP();
	cout<<Sum<<endl;
	return 0;
}
2020/8/19 23:32
加载中...