【网络流】SAP算法

star870126

　　以前用的是Ford-Fulkerson 这是一个用dfs找任意增广路的算法.时间复杂度无从估计
　　
　　Shortest Augmenting Paths(也就是很流行的SAP算法)
　　故名思议,就是找最短的增广路,把EK算法的O(E)时间优化到了O(V),故复杂度为O(V2E)
　　但是可以加上间隙优化，使速度极大提升。
　　
　　用的是Ditch那道题，usaco的一道网络流模板题目



描述
在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。
因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。
作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
格式
PROGRAM NAME:ditch
INPUT FORMAT:
(file ditch.in)
第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫John已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。
第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。
OUTPUT FORMAT:
(file ditch.out)
输出一个整数，即排水的最大流量。
SAMPLE INPUT
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
SAMPLE OUTPUT
50
　　


Ford-Fulkerson


1 const
2   oo=100000000;
3 var
4   a:array[0..200,0..200]of longint;  //流量
5   c:array[0..200]of longint;
6   f:array[0..200]of boolean;
7   ok:boolean;
8   n,m,i,j,x,y,z,sum,ds:longint;
9 function min(x,y:longint):longint;
10   begin
11     if x<y then min:=x else min:=y;
12   end;
13 procedure dfs(x,mflow:longint);
14   var
15     i,y:longint;
16   begin
17     f[x]:=true;
18     if x=n then
19       begin
20         sum:=sum+mflow;
21         ds:=mflow;
22         ok:=true;
23         exit;
24       end;
25     for i:=1 to n do
26     begin
27       if (a[x,i]=0)  or f then continue;
28
29       dfs(i,min(mflow,a[x,i]));
30
31       if ok then  //找到一条增广路径，把相应的流量剪掉。
32       begin
33         dec(a[x,i],ds);
34         inc(a[i,x],ds);
35         exit;
36       end;
37     end;
38   end;
39 begin
40   assign(input,'ditch.in');  reset(input);
41   assign(output,'ditch.out');rewrite(output);
42   readln(m,n);
43   for i:=1 to m do
44     begin
45       readln(x,y,z);
46       a[x,y]:=a[x,y]+z;
47     end;
48   ok:=true;
49   while ok do
50     begin
51       ok:=false;
52       fillchar(f,sizeof(f),false);
53       dfs(1,oo);
54     end;
55
56   writeln(sum);
57   close(input);  close(output);
58 end.

SAP


1 /**
2 *Prob    : ditch
3 *Data    : 2012-6
4 *SOl    : 网络流sap
5 *Author : ZhouHang
6 */
7
8 #include <cstdio>
9 #include <cstring>
10 #include <algorithm>
11
12 #define MaxD 210
13 #define oo 2000000
14
15 using namespace std;
16
17 int n,s,t;
18 int a[MaxD][MaxD],b[MaxD][MaxD];
19 int dis[MaxD],gap[MaxD],pre[MaxD],cur[MaxD];
20
21 int sap()
22 {
23     int u=s,aug=oo,maxflow=0;
24     //cur为优化,当前弧不是允许弧，i更改前一直都不会是允许的
25     //d不变 d[v]不减
26     memset(cur,0,sizeof(cur));
27     memset(pre,0,sizeof(pre));
28     memset(dis,0,sizeof(dis));
29     memset(gap,0,sizeof(gap));
30     gap[0]=n; pre=s;
31     
32     while (dis<n) {
33 loop:    for (int v=cur; v<=n; v++)
34             if (a[v] && dis==dis[v]+1) {
35                 aug = min(aug,a[v]);
36                 pre[v]=u; u=cur=v;
37                 if (v==t) {
38                     maxflow += aug;
39                     for (u = pre; v!=s; v=u,u=pre) {
40                         a[v] -= aug;
41                         a[v] += aug;
42                     }
43                     aug = oo;
44                 }
45                 goto loop;
46             }
47         int mindis=MaxD;
48         for (int v=0; v<=n; v++)
49             if (a[v] && mindis>dis[v]) {
50                 cur=v; mindis = dis[v];
51             }
52             if ((--gap[dis])==0) break;
53             dis = mindis + 1;
54             gap[dis]++;
55             u = pre;
56     }
57     return maxflow;
58 }
59
60 int main()
61 {
62     freopen("ditch.in","r",stdin);
63     freopen("ditch.out","w",stdout);
64     
65     int m,x,y,z;
66     
67     scanf("%d%d",&m,&n);
68     for (int i=1; i<=m; i++) {
69         scanf("%d%d%d",&x,&y,&z);
70         a[x][y]+=z;
71         b[y][x]+=z;
72     }
73
74     s=1; t=n;
75     printf("%d\n",sap());
76
77     fclose(stdin); fclose(stdout);
78     return 0;
79 }
　　
　　邻接表的在这里：
　　POJ 1459 【网络流模板题】
　　本来是邻接矩阵就可以的，但是为了训练，写了个邻接表的。
　　多源多汇的图，建立个超级源，超级汇就可以了，读入比较有意思。
　　题目在这里 ： http://poj.org/problem?id=1459
　　【邻接表里值得注意的是cur数组的运用，这个放的是“当前弧”，所以在某个循环中用了 for(int &i=cur)】


POJ 1459邻接表


  1 /**
  2 *Prob    : Network
  3 *Data    : 2012-6-28
  4 *Sol    : Network -- SAP
  5 *Author : ZhouHang
  6 */
  7
  8 #include <cstdio>
  9 #include <cstring>
10 #include <algorithm>
11
12 #define MaxN 300
13 #define MaxE 200000
14 #define oo 20000000
15
16 using namespace std;
17
18 struct node {
19     int y,c,next,other;
20 } e[MaxE];
21 int n,s,t,tot=0;
22 int a[MaxN],cur[MaxN],pre[MaxN],dis[MaxN],gap[MaxN];
23
24 int SAP()
25 {
26     memset(pre,0,sizeof(pre));
27     memset(dis,0,sizeof(dis));
28     memset(gap,0,sizeof(gap));
29     for (int i=0; i<=n+1; i++)
30         cur = a;
31     gap[0]=n; int u = pre = s, maxflow = 0, aug = oo;
32     
33     while (dis<n) {
34 loop:     for (int &i = cur; i; i=e.next) {
35             int v = e.y;
36             if (e.c && dis==dis[v]+1) {
37                 aug = min(aug,e.c);
38                 pre[v] = u; u=v;
39                 if (v==t) {
40                     maxflow += aug;
41                     for (u=pre; v!=s; v=u,u=pre) {
42                         e[cur].c -= aug;
43                         e[e[cur].other].c += aug;
44                     }
45                     aug = oo;
46                 }
47                 goto loop;
48             }
49         }
50         int mindis = n;
51         for (int i=a; i; i=e.next) {
52             int v = e.y;
53             if (e.c && mindis>dis[v]) {
54                 cur = i; mindis = dis[v];
55             }
56         }
57         if ((--gap[dis])==0) break;
58         dis = mindis+1;
59         gap[dis]++;
60         u = pre;
61     }
62     return maxflow;
63 }
64
65 void insert(int x,int y,int c,int _other)
66 {
67     e[tot].y = y; e[tot].c = c; e[tot].other = _other;
68     e[tot].next = a[x]; a[x] = tot;
69 }
70
71 int main()
72 {
73     freopen("poj1459.in","r",stdin);
74     freopen("poj1459.out","w",stdout);
75     
76     
77     int np,nc,m,x,y,z;
78     while (scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF) {
79         memset(e,0,sizeof(e));
80         memset(a,0,sizeof(a));
81         s=0; t=n+1; tot=0; n+=2;
82         for (int i=1; i<=m; i++) {
83             scanf(" (%d,%d)%d",&x,&y,&z);
84             if (x!=y) {
85                 tot++; insert(x+1,y+1,z,tot+1);
86                 tot++; insert(y+1,x+1,0,tot-1);
87             }
88         }
89         for (int i=1; i<=np; i++) {
90             scanf(" (%d)%d",&x,&z);
91             tot++; insert(s,x+1,z,tot+1);
92             tot++; insert(x+1,s,0,tot-1);
93         }
94         for (int i=1; i<=nc; i++) {
95             scanf(" (%d)%d",&x,&z);
96             tot++; insert(x+1,t,z,tot+1);
97             tot++; insert(t,x+1,0,tot-1);
98             }
99         printf("%d\n",SAP());
100     }
101     
102     
103     fclose(stdin); fclose(stdout);
104     return 0;
105 }
　　
　　还有一道题
　　【POJ 1149】PIGS
　　题解可以看这个 http://www.cppblog.com/y346491470/articles/152830.html
　　下面是我的SAP写法


View Code


  1 /**
  2 *Prob    : pigs
  3 *Data    : 2012-7-20
  4 *Sol    : Sap
  5 */
  6
  7 #include <cstring>
  8 #include <cstdio>
  9 #include <algorithm>
10
11 #define MaxN 510
12 #define MaxM 1010
13 #define oo 20000000
14
15 using namespace std;
16
17 struct node {
18     int y,c,next,other;
19 } e[MaxN*MaxN*2];
20 int cur[MaxN],gap[MaxN],dis[MaxN],a[MaxN],pre[MaxN];
21
22 int n,m,s,t,tot = 0;
23 bool v[MaxM];
24 int num[MaxM];
25
26 void insert(int x,int y,int c,int other)
27 {
28     e[tot].y = y; e[tot].c = c; e[tot].other = other;
29     e[tot].next = a[x]; a[x] = tot;
30 }
31
32 int sap()
33 {
34     memset(pre,0,sizeof(pre));
35     memset(dis,0,sizeof(dis));
36     memset(gap,0,sizeof(gap));
37     for (int i=0; i<=n; i++)
38         cur = a;
39     gap[0] = n; int u = pre = s, maxflow = 0, aug = oo;
40     
41     while (dis<n) {
42 loop: for (int &i = cur; i; i=e.next) {
43         int v = e.y;
44         if (e.c&&dis == dis[v]+1) {
45             aug = min(aug,e.c);
46             pre[v] = u; u = v;
47             if (v==t) {
48                 maxflow += aug;
49                 for (u=pre; v!=s; v=u,u=pre) {
50                     e[cur].c -= aug;
51                     e[e[cur].other].c += aug;
52                 }
53                 aug = oo;
54             }
55             goto loop;
56         }
57       }
58       int tmp = n-1;
59       for (int i=a; i; i=e.next) {
60         int v = e.y;
61         if (e.c&&dis[v]<tmp) {
62             cur = i; tmp = dis[v];
63         }
64       }
65       if ((--gap[dis])==0) break;
66       dis = tmp + 1;
67       gap[dis]++;
68       u = pre;
69     }
70     return maxflow;
71 }
72
73 int main()
74 {
75     freopen("pigs.in","r",stdin);
76     freopen("pigs.out","w",stdout);
77     
78     scanf("%d%d",&m,&n);
79     for (int i=1; i<=m; i++)
80         scanf("%d",&num);
81     
82     int k,kk,buy;
83     s = 0; t = n+1;
84     memset(pre,0,sizeof(pre));
85     memset(v,false,sizeof(v));
86     for (int i=1; i<=n; i++) {
87         scanf("%d",&k);
88         for (int j=1; j<=k; j++) {
89             scanf("%d",&kk);
90             if (!v[kk]) {
91                 v[kk] = true; pre[kk] = i;
92                 tot++; insert(s,i,num[kk],tot+1);
93                 tot++; insert(i,s,0,tot-1);
94             }
95             else {
96                 tot++; insert(pre[kk],i,oo,tot+1);
97                 tot++; insert(i,pre[kk],0,tot-1);
98                 pre[kk] = i;
99             }
100         }
101         scanf("%d",&buy);
102         tot++; insert(i,t,buy,tot+1);
103         tot++; insert(t,i,0,tot-1);
104     }
105     n += 2;
106     
107     int ans = sap();
108     
109     printf("%d\n",ans);
110
111     fclose(stdin); fclose(stdout);
112     return 0;   
113 }
　　
　　
　　另外附上几个链接
　　http://www.cnblogs.com/longdouhzt/archive/2011/09/04/2166187.html
http://hi.baidu.com/supersnowbird/blog/item/7271e18ac5c1441bc9fc7a59.html
　　模板：
　　http://www.notonlysuccess.com/index.php/algorithm-of-network/