为什么这道题的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;
}