源码:

ISAP by pascal

这里不太细讲ISAP的算法过程。

其思路就是能不能不要像DINIC那样搞那么多次BFS,然后ISAP就直接在DFS里面搞了。然后人们发现ISAP有很多可以优化的地方,最突出的就是GAP。

GAP
我们可以知道一个点到汇点的距离,那么当距离为3时,没有任何一个点(GAP[3]=0,GAP[距离]=点数),而2和4都有(GAP[2]=2,GAP[4]=3)。那么直接退出,想都不用想!

我选择ISAP其一是时间复杂度要比DINIC快1.5倍以上,程序复杂度比DINIC少1.5倍以上。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// luogu-judger-enable-o2

Uses math;

var
	//个人习惯:value是流量,reach就是to,cnt就是head
    //gap是GAP优化,dis是分层
        value,reach,cnt,next,gap,dis:array[0..2100000] of longint;
        n,m,source,sink,tot,x,y,sum,i:longint;
    //个人习惯:source是源点,sink是汇点
        maxflow:int64;
    //答案:maxflow

procedure add(x,y,sum:longint); //链式前向星
begin
        inc(tot);
        reach[tot]:=y;
        inc(value[tot],sum);
        next[tot]:=cnt[x];
        cnt[x]:=tot;
end;

function Dfs(now,flow:longint):longint; //当前点和当前最大流量,以下于DINIC差不多
var
        i,k,mindis,ret:longint;
begin
        mindis:=n-1;
        ret:=flow;//赋值一下
        if now=sink then
                exit(flow);

        i:=cnt[now];
        repeat
                if value[i]>0 then
                begin
                        if dis[now]=dis[reach[i]]+1 then
                        begin
                                k:=Dfs(reach[i],min(ret,value[i]));
                                dec(value[i],k);
                                inc(value[i xor 1],k);
                                dec(ret,k);
                                if dis[source]>=n then //不能分层
                                        exit(flow-ret);
                                if ret=0 then //流量没了,直接退出   
                                	break;
                        end;
                        mindis:=min(mindis,dis[reach[i]]);
                end;
                i:=next[i];
        until i=-1;

        if ret=flow then //GAP优化
        begin
                dec(gap[dis[now]]); //本点的位置换了(因为选了边)
                if gap[dis[now]]=0 then
                        dis[source]:=n; 
                dis[now]:=mindis+1; 
                inc(gap[dis[now]]); //这才是本点的位置
        end;
        exit(flow-ret);
end;

begin
        filldword(cnt,sizeof(cnt) div 4,maxlongint*2+1); //清空为-1
        tot:=1;
        
        read(n,m,source,sink);
        for i:=1 to m do
        begin
                read(x,y,sum);
                add(x,y,sum);
                add(y,x,0);//反向边
        end;

        gap[source]:=n;
        while dis[source]<n do //如果还能分层,这个可以慢慢理解
                inc(maxflow,Dfs(source,maxlongint));
        writeln(maxflow);
end.