学步园

用的是我和盾盾研究出来的“距离标号连续最短增广路算法”，实测效果极佳

先贴代码，下次再解释

program syj;<br /> const maxn=105; maxm=maxn*(maxn-1)>>1; oo=maxlongint>>1;<br /> var e,s,t,n,m,nn,ans,i,j,x:longint; ok:boolean;<br /> h,d,b,sl:array[0..maxm+maxn]of longint;<br /> next,point,w,c:array[-(maxm*3+maxn)..maxm*3+maxn]of longint;<br /> v:array[0..maxm+maxn]of boolean;<br /> g:array[1..maxn,1..maxn]of longint;<br /> procedure link(x,y,z:longint);<br /> begin<br /> inc(e); next[e]:=h[x];point[e]:=y;c[e]:=z;w[e]:=1;h[x]:=e;<br /> next[-e]:=h[y];point[-e]:=x;c[-e]:=-z;w[-e]:=0;h[y]:=-e;<br /> end;<br /> procedure dfs(i:longint);<br /> var j,k:longint;<br /> begin<br /> if i=t then begin<br /> inc(ans,b[t]-b[s]);ok:=true;exit;<br /> end;<br /> v[i]:=true; j:=h[i];<br /> while j<>0 do begin<br /> k:=point[j];<br /> if (w[j]>0)and(c[j]+b[i]-b[k]<sl[k]) then sl[k]:=c[j]+b[i]-b[k];<br /> if (w[j]>0)and(c[j]+b[i]=b[k])and not v[k] then begin<br /> dfs(k);<br /> if ok then begin<br /> w[j]:=0;w[-j]:=1;<br /> ok:=ok and(i<>s); //!! many road improving<br /> if ok then exit;<br /> end;<br /> end;<br /> j:=next[j];<br /> end;<br /> end;<br /> function find:boolean;<br /> var i,z:longint;<br /> begin<br /> z:=oo;<br /> for i:=0 to nn do if not v[i]and(sl[i]<z) then z:=sl[i];<br /> if z=oo then exit(false);<br /> for i:=0 to nn do if v[i] then dec(b[i],z);<br /> find:=true;<br /> end;<br /> begin<br /> assign(input,'jsb.in');reset(input);<br /> assign(output,'jsb.out');rewrite(output);<br /> readln(n); m:=n; s:=0;<br /> for i:=1 to n do<br /> for j:=1 to n do begin<br /> read(g[i,j]); if i>=j then continue; x:=g[i,j];<br /> if x=1 then inc(d[j]) else<br /> if x=0 then inc(d[i]) else begin<br /> inc(m); link(m,i,0);link(m,j,0);<br /> link(0,m,0);<br /> end;<br /> end;<br /> t:=m+1; nn:=m+1;<br /> for i:=1 to n do begin<br /> inc(ans,d[i]*d[i]);<br /> for j:=d[i]+1 to n-1 do link(i,t,2*j-1);<br /> end;<br /> while find do begin<br /> fillchar(sl,sizeof(sl),127);<br /> repeat<br /> fillchar(v,sizeof(v),0); ok:=false;<br /> dfs(s);<br /> until not ok;<br /> end;<br /> writeln(n*(n-1)*(n-2)div 6+(n*(n-1)div 2-ans)div 2);<br /> close(input);close(output);<br /> end.<br />