NOI2006 最大获利

在网上的题解都说的那么轻松，可我打了3个小时，算法换了无数。最终也是加inline优化才过的，唉

最大权闭合子图，模型很简单但是后两个数据大了点，

第一个算法：指针链表+dinic 最大点80s++

View Code

  1 program profit(input,output);
  2 const
  3    oo = 199500714;
  4 type
  5    node    = ^link;
  6    link    = record
  7          goal : longint;
  8          flow : longint;
  9          next : node;
 10       end;
 11 var
 12    l      : array[0..60000] of node;
 13    q      : array[0..60000] of longint;
 14    d      : array[0..60000] of longint;
 15    s,t      : longint;
 16    n,m      : longint;
 17    answer : int64;
 18 procedure add(xx,yy,cc: longint );
 19 var
 20    tt : node;
 21 begin
 22    new(tt);
 23    tt^.flow:=cc;
 24    tt^.goal:=yy;
 25    tt^.next:=l[xx];
 26    l[xx]:=tt;
 27 end; { add }
 28 procedure init;
 29 var
 30    i,xx,yy,cc : longint;
 31 begin
 32    readln(n,m);
 33    s:=0;
 34    t:=m+n+1;
 35    for i:=s to t do
 36       l[i]:=nil;
 37    for i:=1 to n do
 38    begin
 39       read(cc);
 40       add(s,i,cc);
 41       add(i,s,0);
 42    end;
 43    readln;
 44    answer:=0;
 45    for i:=1 to m do
 46    begin
 47       readln(xx,yy,cc);
 48       add(xx,i+n,oo);
 49       add(i+n,xx,0);
 50       add(yy,i+n,oo);
 51       add(i+n,yy,0);
 52       add(i+n,t,cc);
 53       add(t,i+n,0);
 54       inc(answer,cc);
 55    end;
 56 end; { init }
 57 function bfs(now :longint ):boolean;
 58 var
 59    i,head,tail : longint;
 60    tt           : node;
 61 begin
 62    for i:=s to t do
 63       d[i]:=-1;
 64    head:=0;
 65    tail:=1;
 66    q[1]:=now;
 67    d[now]:=0;
 68    while head<tail do
 69    begin
 70       inc(head);
 71       tt:=l[q[head]];
 72       while tt<>nil do
 73       begin
 74      if tt^.flow>0 then
 75         if d[tt^.goal]=-1 then
 76         begin
 77            d[tt^.goal]:=d[q[head]]+1;
 78            inc(tail);
 79            q[tail]:=tt^.goal;
 80         end;
 81      tt:=tt^.next;
 82       end;
 83    end;
 84    if d[t]=-1 then
 85       exit(false);
 86    exit(true);
 87 end; { bfs }
 88 function min(aa,bb :longint ):longint;
 89 begin
 90    if aa>bb then
 91       exit(bb);
 92    exit(aa);
 93 end; { min }
 94 function dfs(now,minf: longint ):longint;
 95 var
 96    tt  : node;
 97    ttt : node;
 98    tmp : longint;
 99 begin
100    if now=t then
101       exit(minf);
102    tt:=l[now];
103    while tt<>nil do
104    begin
105       if d[tt^.goal]=d[now]+1 then
106      if tt^.flow>0 then
107      begin
108         tmp:=dfs(tt^.goal,min(minf,tt^.flow));
109         if tmp<>0 then
110         begin
111            dec(tt^.flow,tmp);
112            ttt:=l[tt^.goal];
113            while ttt<>nil do
114            begin
115           if ttt^.goal=now then
116           begin
117              inc(ttt^.flow,tmp);
118              break;
119           end;
120           ttt:=ttt^.next;
121            end;
122            exit(tmp);
123         end;
124      end;
125       tt:=tt^.next;
126    end;
127    exit(0);
128 end; { dfs }
129 procedure dinic();
130 var
131    tmp : longint;
132 begin
133    while bfs(s) do
134    begin
135       tmp:=dfs(s,oo);
136       while tmp<>0 do
137       begin
138      dec(answer,tmp);
139      tmp:=dfs(s,oo);
140       end;
141    end;
142 end; { dinic }
143 procedure print;
144 begin
145    writeln(answer);
146 end; { print }
147 begin
148    assign(input,'profit.in');reset(input);
149    assign(output,'profit.out');rewrite(output);
150    init();
151    dinic();
152    print();
153    close(input);
154    close(output);
155 end.

第二个算法：前向星存储+dinic 最大点55s++

View Code

  1 program profit(input,output);
  2 const
  3    oo = 199500714;
  4 var
  5    f,x,y,c : array[0..500000] of longint;
  6    q       : array[0..100000] of longint;
  7    d       : array[0..100000] of longint;
  8    s,t       : longint;
  9    n,m       : longint;
 10    answer  : int64;
 11    tot       : longint;
 12 procedure add(xx,yy,cc: longint );
 13 begin
 14    inc(tot);
 15    x[tot]:=xx;
 16    y[tot]:=yy;
 17    c[tot]:=cc;
 18 end; { add }
 19 procedure init;
 20 var
 21    i,xx,yy,cc : longint;
 22 begin
 23    readln(n,m);
 24    s:=0;
 25    t:=m+n+1;
 26    for i:=1 to n do
 27    begin
 28       read(cc);
 29       add(s,i,cc);
 30       add(i,s,0);
 31    end;
 32    readln;
 33    answer:=0;
 34    for i:=1 to m do
 35    begin
 36       readln(xx,yy,cc);
 37       add(xx,i+n,oo);
 38       add(i+n,xx,0);
 39       add(yy,i+n,oo);
 40       add(i+n,yy,0);
 41       add(i+n,t,cc);
 42       add(t,i+n,0);
 43       inc(answer,cc);
 44    end;
 45 end; { init }
 46 procedure swap(var aa,bb :longint );
 47 var
 48    tt : longint;
 49 begin
 50    tt:=aa;
 51    aa:=bb;
 52    bb:=tt;
 53 end; { swap }
 54 procedure sort(p,q :longint );
 55 var
 56    i,j,mid : longint;
 57 begin
 58    i:=p;
 59    j:=q;
 60    mid:=x[(i+j)>>1];
 61    repeat
 62       while x[i]<mid do
 63      inc(i);
 64       while x[j]>mid do
 65      dec(j);
 66       if i<=j then
 67       begin
 68      swap(x[i],x[j]);
 69      swap(y[i],y[j]);
 70      swap(c[i],c[j]);
 71      inc(i);
 72      dec(j);
 73       end;
 74    until i>j;
 75    if i<q then sort(i,q);
 76    if j>p then sort(p,j);
 77 end; { sort }
 78 procedure make;
 79 var
 80    i : longint;
 81 begin
 82    fillchar(f,sizeof(f),0);
 83    for i:=1 to tot do
 84       if f[x[i]]=0 then
 85      f[x[i]]:=i;
 86    f[t+1]:=tot+1;
 87    for i:=t downto s do
 88       if f[i]=0 then
 89      f[i]:=f[i+1];
 90 end; { make }
 91 function bfs(now: longint ):boolean;
 92 var
 93    i,head,tail : longint;
 94 begin
 95    for i:=s to t do
 96       d[i]:=-1;
 97    head:=0;
 98    tail:=1;
 99    q[1]:=now;
100    d[now]:=0;
101    while head<tail do
102    begin
103       inc(head);
104       for i:=f[q[head]] to f[q[head]+1]-1 do
105       begin
106      if c[i]>0 then
107         if d[y[i]]=-1 then
108         begin
109            d[y[i]]:=d[q[head]]+1;
110            inc(tail);
111            q[tail]:=y[i];
112         end;
113       end;
114    end;
115    if d[t]=-1 then
116       exit(false);
117    exit(true);
118 end; { bfs }
119 function min(aa,bb :longint ):longint;
120 begin
121    if aa>bb then
122       exit(bb);
123    exit(aa);
124 end; { min }
125 function dfs(now,minf: longint ):longint;
126 var
127    i,j : longint;
128    tmp : longint;
129 begin
130    if now=t then
131       exit(minf);
132    for i:=f[now] to f[now+1]-1 do
133       if d[y[i]]=d[x[i]]+1 then
134      if c[i]>0 then
135      begin
136         tmp:=dfs(y[i],min(minf,c[i]));
137         if tmp<>0 then
138         begin
139            dec(c[i],tmp);
140            for j:=f[y[i]] to f[y[i]+1]-1 do
141           if y[j]=now then
142           begin
143              inc(c[j],tmp);
144              break;
145           end;
146            exit(tmp);
147         end;
148      end;
149    exit(0);
150 end; { dfs }
151 procedure dinic();
152 var
153    tmp : longint;
154 begin
155    while bfs(s) do
156    begin
157       tmp:=dfs(s,oo);
158       while tmp<>0 do
159       begin
160      dec(answer,tmp);
161      tmp:=dfs(s,oo);
162       end;
163    end;
164 end; { dinic }
165 procedure print;
166 begin
167    writeln(answer);
168 end; { print }
169 begin
170    assign(input,'profit.in');reset(input);
171    assign(output,'profit.out');rewrite(output);
172    init();
173    sort(1,tot);
174    make;
175    dinic();
176    print();
177    close(input);
178    close(output);
179 end.

第三个算法：前向星存储+SAP 最大点3s++ 加上inline，1.8s

View Code

  1 {$inline on}
  2 program profit(input,output);
  3 const
  4    oo = 199500714;
  5 var
  6    f,x,y,c : array[0..500000] of longint;
  7    h,vh       : array[0..100000] of longint;
  8    s,t       : longint;
  9    n,m       : longint;
 10    answer  : int64;
 11    tot       : longint;
 12    tmpflow : longint;
 13    can       : boolean;
 14 procedure add(xx,yy,cc: longint ); inline;
 15 begin
 16    inc(tot);
 17    x[tot]:=xx;
 18    y[tot]:=yy;
 19    c[tot]:=cc;
 20 end; { add }
 21 procedure init; inline;
 22 var
 23    i,xx,yy,cc : longint;
 24 begin
 25    readln(n,m);
 26    s:=0;
 27    t:=m+n+1;
 28    for i:=1 to n do
 29    begin
 30       read(cc);
 31       add(s,i,cc);
 32       add(i,s,0);
 33    end;
 34    readln;
 35    answer:=0;
 36    for i:=1 to m do
 37    begin
 38       readln(xx,yy,cc);
 39       add(xx,i+n,oo);
 40       add(i+n,xx,0);
 41       add(yy,i+n,oo);
 42       add(i+n,yy,0);
 43       add(i+n,t,cc);
 44       add(t,i+n,0);
 45       inc(answer,cc);
 46    end;
 47 end; { init }
 48 procedure swap(var aa,bb :longint ); inline;
 49 var
 50    tt : longint;
 51 begin
 52    tt:=aa;
 53    aa:=bb;
 54    bb:=tt;
 55 end; { swap }
 56 procedure sort(p,q :longint ); inline;
 57 var
 58    i,j,mid : longint;
 59 begin
 60    i:=p;
 61    j:=q;
 62    mid:=x[(i+j)>>1];
 63    repeat
 64       while x[i]<mid do
 65      inc(i);
 66       while x[j]>mid do
 67      dec(j);
 68       if i<=j then
 69       begin
 70      swap(x[i],x[j]);
 71      swap(y[i],y[j]);
 72      swap(c[i],c[j]);
 73      inc(i);
 74      dec(j);
 75       end;
 76    until i>j;
 77    if i<q then sort(i,q);
 78    if j>p then sort(p,j);
 79 end; { sort }
 80 procedure make; inline;
 81 var
 82    i : longint;
 83 begin
 84    fillchar(f,sizeof(f),0);
 85    for i:=1 to tot do
 86       if f[x[i]]=0 then
 87      f[x[i]]:=i;
 88    f[t+1]:=tot+1;
 89    for i:=t downto s do
 90       if f[i]=0 then
 91      f[i]:=f[i+1];
 92 end; { make }
 93 procedure dfs(now : longint ); inline;
 94 var
 95    min,tmp : longint;
 96    i,j       : longint;
 97 begin
 98    min:=t;
 99    tmp:=tmpflow;
100    if now=t then
101    begin
102       can:=true;
103       dec(answer,tmpflow);
104       exit;
105    end;
106    for i:=f[now] to f[now+1]-1 do
107       if c[i]>0 then
108       begin
109      if h[y[i]]+1=h[now] then
110      begin
111         if c[i]<tmpflow then
112            tmpflow:=c[i];
113         dfs(y[i]);
114         if h[s]>=t+1 then
115            exit;
116         if can then
117            break;
118         tmpflow:=tmp;
119      end;
120      if h[y[i]]<min then
121         min:=h[y[i]];
122       end;
123    if not can then
124    begin
125       dec(vh[h[now]]);
126       if vh[h[now]]=0 then
127      h[s]:=t+1;
128       h[now]:=min+1;
129       inc(vh[h[now]]);
130    end
131    else
132    begin
133       dec(c[i],tmpflow);
134       for j:=f[y[i]] to f[y[i]+1]-1 do
135      if y[j]=now then
136      begin
137         inc(c[j],tmpflow);
138         break;
139      end;
140    end;
141 end; { dfs }
142 procedure SAP(); inline;
143 begin
144    fillchar(h,sizeof(h),0);
145    fillchar(vh,sizeof(vh),0);
146    vh[0]:=t+1;
147    while h[s]<t+1 do
148    begin
149       tmpflow:=oo;
150       can:=false;
151       dfs(s);
152    end;
153 end; { SAP }
154 procedure print; inline;
155 begin
156    writeln(answer);
157 end; { print }
158 begin
159    assign(input,'profit.in');reset(input);
160    assign(output,'profit.out');rewrite(output);
161    init();
162    sort(1,tot);
163    make;
164    SAP;
165    print();
166    close(input);
167    close(output);
168 end.