蛋疼的网络流，想了一会儿没思路看题解了。由于模型转换太神奇，自己百度。我这儿就贴代码了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | 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. |
评论 (0)
