还是同一类最小割问题

对于只要记住，建图是来最小化损失，

最大化收益是所有收益-最小取不到的收益

首先对于每个经理i，如果不取，必然有signma(w[i,j])收益会得不到（这里我们先不考虑额外的损失）；

如果取，必然会损失a[i](其实这个也不是收益，只是我们最后用sum-mincut时，sum不包括a[i],就相当于损失了）；

下面考虑额外损失，对于i,j不在同一集合内（假设i被雇佣而j不被雇佣），会再损失2*w[i,j];

为什么是2倍呢，从建图来看，如果这样做最小割，雇佣i,不雇佣j,那么w[i,j]这个收益会被取到一次，而事实上不仅取不到还要额外损失，然后我们还要再减去一个经理之间的额外影响（由题意），所以是2倍；

然后分析完之后带入例子验证一下即可；

建图就不多说了

1 const inf=2147483647;  2 type node=record  3        next,flow,point:longint;  4      end;  5   6 var edge:array[0..4400010] of node;  7     d,p,cur,pre,h,numh:array[0..1010] of longint;  8     t,len,n,m,i,j,x,s,ans:longint;  9  10 function min(a,b:longint):longint; 11   begin 12     if a>b then exit(b) else exit(a); 13   end; 14  15 procedure add(x,y,f:longint); 16   begin 17     inc(len); 18     edge[len].point:=y; 19     edge[len].flow:=f; 20     edge[len].next:=p[x]; 21     p[x]:=len; 22   end; 23  24 function sap:longint; 25   var neck,i,j,tmp,u,q:longint; 26   begin 27     numh[0]:=t+1; 28     sap:=0; 29     neck:=inf; 30     for i:=0 to t do 31       cur[i]:=p[i]; 32     u:=0; 33     while h[0]
      
       -1 do 38       begin 39         j:=edge[i].point; 40         if (edge[i].flow>0) and (h[u]=h[j]+1) then 41         begin 42           cur[u]:=i; 43           pre[j]:=u; 44           neck:=min(neck,edge[i].flow); 45           u:=j; 46           if u=t then 47           begin 48             while u<>0 do 49             begin 50               u:=pre[u]; 51               j:=cur[u]; 52               dec(edge[j].flow,neck); 53               inc(edge[j xor 1].flow,neck); 54             end; 55             sap:=sap+neck; 56             neck:=inf; 57           end; 58           break; 59         end; 60         i:=edge[i].next; 61       end; 62       if i=-1 then 63       begin 64         dec(numh[h[u]]); 65         if numh[h[u]]=0 then exit; 66         i:=p[u]; 67         tmp:=t; 68         q:=-1; 69         while i<>-1 do 70         begin 71           j:=edge[i].point; 72           if (edge[i].flow>0) and (h[j]
       
        0 then 83         begin 84           u:=pre[u]; 85           neck:=d[u]; 86         end; 87       end; 88     end; 89   end; 90  91 begin 92   len:=-1; 93   readln(n); 94   fillchar(p,sizeof(p),255); 95   t:=n+1; 96   for i:=1 to n do 97   begin 98     read(x); 99     add(i,t,x);100     add(t,i,0);101   end;102   for i:=1 to n do103   begin104     s:=0;105     for j:=1 to n do106     begin107       read(x);108       s:=s+x;109       if i<>j then110       begin111         add(i,j,x shl 1);112         add(j,i,0);113       end;114     end;115     add(0,i,s);116     add(i,0,0);117     ans:=ans+s;118   end;119   writeln(ans-sap);120 end.