道路修建（网络流）

  1 const INF=2000000000;
  2 const maxn=4008;
  3 var r:array[0..maxn] of longint;
  4     eg:array[0..1000008] of record u,v,w,nt:longint; end;
  5     el:longint;
  6     lt:array[0..maxn] of longint;
  7     h:array[0..maxn] of longint;
  8     b:array[0..10008] of longint;
  9     i,j,k,n,s,t,m,x,y:longint;
 10 function op(i,j:longint):longint; inline;
 11 begin
 12     exit((i-1)*n+j);
 13 end;
 14 function calc(x,y:longint):longint; inline;
 15 begin
 16     exit(trunc(10*ln(233*(x-y)*(x-y)+1)));
 17 end;
 18 procedure adt(u,v,w:longint);
 19 begin
 20     inc(el);
 21     eg[el].u:=u;
 22     eg[el].v:=v;
 23     eg[el].w:=w;
 24     eg[el].nt:=lt[u];
 25     lt[u]:=el;
 26 end;
 27 procedure add(u,v,w:longint);
 28 begin
 29      //   writeln(u,' ',v,' ',w);
 30     adt(u,v,w); adt(v,u,0);
 31 end;
 32 procedure bfs;
 33 var i,l,r,x:longint;
 34 begin
 35     fillchar(h,sizeof(h),$7f);
 36     h[t]:=0;
 37     l:=1; r:=1; b[1]:=t;
 38     while l<=r do
 39     begin
 40         x:=b[l];
 41         i:=lt[x];
 42         while i<>0 do
 43         begin
 44             if (h[eg[i].v]>=n) and (eg[i xor 1].w>0) then
 45             begin
 46                 inc(r);
 47                 b[r]:=eg[i].v;
 48                 h[eg[i].v]:=h[x]+1;
 49             end;
 50             i:=eg[i].nt;
 51         end;
 52         inc(l);
 53     end;
 54 end;
 55 function min(a,b:longint):longint; inline;
 56 begin
 57     if a<b then exit(a) else exit(b);
 58 end;
 59 function dfs(u,inl:longint):longint;
 60 var i,v,outl:longint;
 61 begin
 62     if u=t then exit(inl);
 63     dfs:=0;
 64     i:=lt[u];
 65     while i<>0 do
 66     begin
 67         v:=eg[i].v;
 68         if (eg[i].w>0) and (h[u]=h[v]+1) then
 69         begin
 70             outl:=dfs(v,min(eg[i].w,inl));
 71             dec(inl,outl);
 72             inc(dfs,outl);
 73             dec(eg[i].w,outl);
 74             inc(eg[i xor 1].w,outl);
 75             if inl=0 then break;
 76         end;
 77         i:=eg[i].nt;
 78     end;
 79     if inl=0 then h[u]:=-1;
 80 end;
 81 function dinic:longint;
 82 var sum:longint;
 83 begin
 84     bfs;
 85     sum:=0;
 86     while h[s]<n do
 87     begin
 88         sum:=sum+dfs(s,INF);
 89         bfs;
 90         //writeln(sum);
 91     end;
 92     exit(sum);
 93 end;
 94 begin
 95     //assign(input,'1.in');reset(input);
 96     el:=1;
 97     readln(n,m);
 98     for i:=1 to n do read(r[i]);
 99     s:=0; t:=n*n+1;
100     for i:=1 to n do
101     begin
102         if i=1 then add(s,op(i,1),calc(0,r[i]))
103                else add(s,op(i,1),INF);
104         for j:=2 to n do
105             if i<>1 then
106                 add(op(i,j-1),op(i,j),calc(j-1,r[i]))
107             else
108                 add(op(i,j-1),op(i,j),INF);
109         if i=1 then add(op(i,n),t,INF) else add(op(i,n),t,calc(n,r[i]))
110     end;
111  
112     for i:=1 to m do
113     begin
114         readln(x,y);
115         for k:=2 to n do
116         begin
117             add(op(x,k),op(y,k-1),INF);
118             add(op(y,k),op(x,k-1),INF);
119         end;
120     end;
121     n:=n*n+1;
122     writeln(dinic);
123 end.
道路修建 （网络流）

道路修建（网络流）
