jiry_2's Blog

蛋疼的网络流，想了一会儿没思路看题解了。由于模型转换太神奇，自己百度。我这儿就贴代码了。

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.