【BZOJ3894】文理分科（最小割）

题意：给定一个m*n的矩阵，每个格子的人可以学文或者学理，学文和学理各有一个满意度，

如果以某人为中心的十字内所有人都学文或者学理还会得到一个额外满意度，求最大满意度之和

N,M<=100,读入数据均<=500

思路：RYZ作业

惊奇地发现其他人一年前就A了

每个人选文选理很好连，源集连文，汇集连理，文理连OO

对于十字，将每一个十字看作一个点，以都选文举例

源点连到这个点，容量为额外的满意度

这个点连十字中每个点选文，容量为OO

选理同理

答案为所有的满意度之和减去最小割，即放弃的满意度

花费最小的代价，使源集与汇集之间没有流量

  1 const dx:array[1..4]of longint=(-1,1,0,0);
  2       dy:array[1..4]of longint=(0,0,-1,1);
  3 var head,vet,next,len,gap,dis,fan:array[0..1100000]of longint;
  4     a,num:array[1..100,1..100,1..4]of longint;
  5     n,m,tot,i,j,sum,s,source,src,k,x,y:longint;
  6 
  7 procedure add(a,b,c:longint);
  8 begin
  9  inc(tot);
 10  next[tot]:=head[a];
 11  vet[tot]:=b;
 12  len[tot]:=c;
 13  head[a]:=tot;
 14 
 15  inc(tot);
 16  next[tot]:=head[b];
 17  vet[tot]:=a;
 18  len[tot]:=0;
 19  head[b]:=tot;
 20 end;
 21 
 22 function min(x,y:longint):longint;
 23 begin
 24  if x<y then exit(x);
 25  exit(y);
 26 end;
 27 
 28 function dfs(u,aug:longint):longint;
 29 var e,v,val,flow,t:longint;
 30 begin
 31  if u=src then exit(aug);
 32  e:=head[u]; val:=s-1; flow:=0;
 33  while e<>0 do
 34  begin
 35   v:=vet[e];
 36   if len[e]>0 then
 37   begin
 38    if dis[u]=dis[v]+1 then
 39    begin
 40     t:=dfs(v,min(len[e],aug-flow));
 41     len[e]:=len[e]-t;
 42     len[fan[e]]:=len[fan[e]]+t;
 43     flow:=flow+t;
 44     if dis[source]>=s then exit(flow);
 45     if aug=flow then break;
 46    end;
 47    val:=min(val,dis[v]);
 48   end;
 49   e:=next[e];
 50  end;
 51  if flow=0 then
 52  begin
 53   dec(gap[dis[u]]);
 54   if gap[dis[u]]=0 then dis[source]:=s;
 55   dis[u]:=val+1;
 56   inc(gap[dis[u]]);
 57  end;
 58  exit(flow);
 59 end;
 60 
 61 function maxflow:longint;
 62 var ans:longint;
 63 begin
 64  fillchar(gap,sizeof(gap),0);
 65  fillchar(dis,sizeof(dis),0);
 66  gap[0]:=s; ans:=0;
 67  while dis[source]<s do ans:=ans+dfs(source,maxlongint);
 68  exit(ans);
 69 end;
 70 
 71 begin
 72  assign(input,'bzoj3894.in'); reset(input);
 73  assign(output,'bzoj3894.out'); rewrite(output);
 74  readln(n,m);
 75  for i:=1 to 1100000 do
 76   if i and 1=1 then fan[i]:=i+1
 77    else fan[i]:=i-1;
 78  for i:=1 to 4 do
 79   for j:=1 to n do
 80    for k:=1 to m do
 81    begin
 82     read(a[j,k,i]);
 83     inc(s); num[j,k,i]:=s;
 84     sum:=sum+a[j,k,i];
 85    end;
 86  source:=s+1; src:=s+2;
 87  s:=s+2;
 88  for i:=1 to n do
 89   for j:=1 to m do add(source,num[i,j,1],a[i,j,1]);
 90  for i:=1 to n do
 91   for j:=1 to m do
 92   begin
 93    add(source,num[i,j,3],a[i,j,3]);
 94    for k:=1 to 4 do
 95    begin
 96     x:=i+dx[k]; y:=j+dy[k];
 97     if (x>0)and(x<=n)and(y>0)and(y<=m) then add(num[i,j,3],num[x,y,1],maxlongint);
 98    end;
 99    add(num[i,j,3],num[i,j,1],maxlongint);
100   end;
101  for i:=1 to n do
102   for j:=1 to m do add(num[i,j,1],num[i,j,2],maxlongint);
103  for i:=1 to n do
104   for j:=1 to m do add(num[i,j,2],src,a[i,j,2]);
105  for i:=1 to n do
106   for j:=1 to m do
107   begin
108    add(num[i,j,4],src,a[i,j,4]);
109    for k:=1 to 4 do
110    begin
111     x:=i+dx[k]; y:=j+dy[k];
112     if (x>0)and(x<=n)and(y>0)and(y<=m) then add(num[x,y,2],num[i,j,4],maxlongint);
113    end;
114    add(num[i,j,2],num[i,j,4],maxlongint);
115   end;
116  writeln(sum-maxflow);
117 end.
118 
119 
120 
121 
122  close(input);
123  close(output);
124 end.