蛋疼的网络流,想了一会儿没思路看题解了。由于模型转换太神奇,自己百度。我这儿就贴代码了。
program p2597;
type
bian=record
next,point,f,w:longint;
end;
var
b:array[0..100000] of bian;
p,d,inw,after:array[0..10000] of longint;
pd:array[0..20000] of boolean;
bi:array[1..200,1..200] of longint;
x:array[1..500000] of longint;
k,len,n,long,i,j:longint;
procedure ade(k1,k2,k3,k4:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
b[len].f:=k3;
b[len].w:=k4;
p[k1]:=len;
end;
procedure add(k1,k2,k3,k4:longint);
begin
ade(k1,k2,k3,k4);
ade(k2,k1,0,-k4);
end;
function spfa:boolean;
var
i,j,head,now:longint;
begin
fillchar(after,sizeof(after),-1);
fillchar(pd,sizeof(pd),false);
fillchar(d,sizeof(d),$3f);
head:=1; now:=0; pd[0]:=true; x[1]:=0; d[0]:=0;
while head<>now do begin
now:=now+1;
i:=p[x[now]];
while i<>-1 do begin
j:=b[i].point;
if (d[x[now]]+b[i].w<d[j]) and (b[i].f>0) then begin
d[j]:=d[x[now]]+b[i].w;
after[j]:=i;
if pd[j]=false then begin
pd[j]:=true;
head:=head+1;
x[head]:=j;
end;
end;
i:=b[i].next;
end;
pd[x[now]]:=false;
end;
if after[n*(n-1) div 2+n+1]=-1 then exit(false) else exit(true);
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function change:longint;
var
i,j,k,ans,num:longint;
begin
i:=n*(n-1) div 2+n+1; j:=after[i]; k:=maxlongint;
while j<>-1 do begin
k:=min(k,b[j].f);
i:=b[j xor 1].point;
j:=after[i];
end;
i:=n*(n-1) div 2+n+1; j:=after[i]; num:=0;
while j<>-1 do begin
num:=num+k*b[j].w;
inc(b[j xor 1].f,k);
dec(b[j].f,k);
i:=b[j xor 1].point;
j:=after[i];
end;
exit(num);
end;
function dinic:longint;
var
ans:longint;
begin
ans:=0;
while spfa=true do
ans:=ans+change;
exit(ans);
end;
function find(k:longint):longint;
var
i,j:longint;
begin
i:=p[k];
while i<>-1 do begin
if (b[i].f=0) then exit(b[i].point);
i:=b[i].next;
end;
end;
begin
fillchar(b,sizeof(b),0);
fillchar(p,sizeof(p),-1);
fillchar(inw,sizeof(inw),0);
len:=-1;
readln(n); long:=0;
for i:=1 to n do
for j:=1 to n do begin
read(k);
if i>=j then continue;
inc(long);
if k=0 then begin
add(long,n*(n-1) div 2+i,1,0);
inc(inw[i]);
end else if k=1 then begin
add(long,n*(n-1) div 2+j,1,0);
inc(inw[j]);
end else if k=2 then begin
add(long,n*(n-1) div 2+i,1,0);
add(long,n*(n-1) div 2+j,1,0);
inc(inw[i]); inc(inw[j]);
end;
end;
for i:=1 to n do
for j:=1 to inw[i] do
add(n*(n-1) div 2+i,n*(n-1) div 2+n+1,1,j*2-1);
for i:=1 to n*(n-1) div 2 do
add(0,i,1,0);
writeln((n*(n-1)*(n-2) div 3+n*(n-1) div 2-dinic) div 2);
long:=0;
fillchar(bi,sizeof(bi),0);
for i:=1 to n do
for j:=i+1 to n do begin
inc(long);
if find(long)-n*(n-1) div 2=i then bi[i,j]:=0 else bi[i,j]:=1;
bi[j,i]:=1-bi[i,j];
end;
for i:=1 to n do begin
for j:=1 to n do
write(bi[i,j],' ');
writeln;
end;
end.