线性规划与网络流24题运输问题（最裸的费用流了）

存费用流模板
用sfpa算出最小费用和路径，沿这条路径增广
  1 const
  2         inf=maxlongint;
  3 var
  4         n,m:longint;
  5         map,a,w:array[0..120,0..120]of longint;
  6 
  7 procedure init;
  8 var
  9         i,j:longint;
 10 begin
 11         read(m,n);
 12         for i:=1 to m do
 13           read(map[0,i]);
 14         for i:=1 to n do
 15           read(map[m+i,n+m+1]);
 16         for i:=1 to m do
 17           for j:=1 to n do
 18             begin
 19               read(w[i,m+j]);
 20               w[m+j,i]:=-w[i,m+j];
 21               map[i,m+j]:=inf;
 22             end;
 23 end;
 24 
 25 var
 26         flag,d,dis,pre:array[0..120]of longint;
 27         time:longint;
 28 
 29 function spfa:boolean;
 30 var
 31         i,head,tail,num:longint;
 32 begin
 33         head:=1;
 34         tail:=1;
 35         num:=1;
 36         inc(time);
 37         for i:=1 to n+m+1 do
 38           dis[i]:=inf;
 39         dis[0]:=0;
 40         d[1]:=0;
 41         flag[0]:=time;
 42         while num>0 do
 43           begin
 44                 for i:=1 to n+m+1 do
 45                   if (a[d[head],i]>0)and(dis[d[head]]+w[d[head],i]<dis[i]) then
 46                   begin
 47                         dis[i]:=dis[d[head]]+w[d[head],i];
 48                         pre[i]:=d[head];
 49                         if flag[i]<>time then
 50                         begin
 51                           flag[i]:=time;
 52                           inc(num);
 53                           tail:=tail mod(n+m+1)+1;
 54                           d[tail]:=i;
 55                         end;
 56                   end;
 57                 flag[d[head]]:=time-1;
 58                 head:=head mod(n+m+1)+1;
 59                 dec(num);
 60           end;
 61         if dis[n+m+1]=inf then exit(false);
 62         exit(true);
 63 end;
 64 
 65 procedure work;
 66 var
 67         i,j,aug,ans:longint;
 68 begin
 69         for i:=0 to n+m+1 do
 70           for j:=0 to n+m+1 do
 71             a[i,j]:=map[i,j];
 72         ans:=0;
 73         while spfa do
 74           begin
 75             aug:=inf;
 76             i:=n+m+1;
 77             while i<>0 do
 78               begin
 79                 j:=pre[i];
 80                 if a[j,i]<aug then aug:=a[j,i];
 81                 i:=j;
 82               end;
 83             inc(ans,dis[n+m+1]*aug);
 84             i:=n+m+1;
 85             while i<>0 do
 86               begin
 87                 j:=pre[i];
 88                 inc(a[i,j],aug);
 89                 dec(a[j,i],aug);
 90                 i:=j;
 91               end;
 92           end;
 93         writeln(ans);
 94         ans:=0;
 95         for i:=1 to m do
 96           for j:=1 to n do
 97             begin
 98               w[i,j+m]:=-w[i,j+m];
 99               w[j+m,i]:=-w[j+m,i];
100             end;
101         for i:=0 to n+m+1 do
102           for j:=0 to n+m+1 do
103             a[i,j]:=map[i,j];
104         ans:=0;
105         while spfa do
106           begin
107             aug:=inf;
108             i:=n+m+1;
109             while i<>0 do
110               begin
111                 j:=pre[i];
112                 if a[j,i]<aug then aug:=a[j,i];
113                 i:=j;
114               end;
115             inc(ans,dis[n+m+1]*aug);
116             i:=n+m+1;
117             while i<>0 do
118               begin
119                 j:=pre[i];
120                 inc(a[i,j],aug);
121                 dec(a[j,i],aug);
122                 i:=j;
123               end;
124           end;
125         writeln(-ans);
126 end;
127 
128 begin
129     assign(input,'trans.in');
130     reset(input);
131     assign(output,'trans.out');
132     rewrite(output);
133         init;
134         work;
135     close(input);
136     close(output);
137 end.
View Code
线性规划与网络流24题 运输问题（最裸的费用流了）

线性规划与网络流24题运输问题（最裸的费用流了）
