bzoj 3996 [TJOI2015]线性代数——最小割

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3996

b[ i ][ j ] 要计入贡献，当且仅当 a[ i ] = 1 , a[ j ] = 1 ；-c[ i ] 要计入贡献，当且仅当 a[ i ] = 1；所以建一排 b 的点，建一排 a 的点，源点向 b 的点连它们价值容量的边，b 向它对应的两个 a 连 INF ； a 向汇点连它对应的 c 容量的边；割源点到 b 的边表示不选该 b ，割 a 到汇点的边表示选该 a 。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,N=*+,INF=N*;

int n,cnt,hd[N],xnt=,cur[N],ans;

int dfn[N],q[N],he,tl;bool vis[N];

struct Ed{

  int to,nxt,cap;

  Ed(int a=,int b=,int c=):to(a),nxt(b),cap(c) {}

}ed[N*];

void add(int x,int y,int z)

{

  ed[++xnt]=Ed(y,hd[x],z);hd[x]=xnt;

  ed[++xnt]=Ed(x,hd[y],);hd[y]=xnt;

}

bool bfs()

{

  memset(dfn,,sizeof dfn);

  q[he=tl=]=;vis[]=;dfn[]=;

  while(he<=tl)

    {

      int k=q[he++];vis[k]=;//he++

      for(int i=hd[k],v;i;i=ed[i].nxt)

    if(!dfn[v=ed[i].to]&&ed[i].cap)

      dfn[v]=dfn[k]+,q[++tl]=v;

    }

  return dfn[cnt];

}

int dinic(int cr,int flow)

{

  if(cr==cnt)return flow;

  int use=;

  for(int& i=cur[cr],v;i;i=ed[i].nxt)

    if(dfn[v=ed[i].to]==dfn[cr]+&&ed[i].cap)

      {

    int tmp=dinic(v,min(flow-use,ed[i].cap));

    if(!tmp)dfn[v]=;

    use+=tmp;ed[i].cap-=tmp;ed[i^].cap+=tmp;

    if(use==flow)return use;

      }

  return use;

}

int main()

{

  scanf("%d",&n);cnt=n;

  for(int i=;i<=n;i++)

    for(int j=,d;j<=n;j++)

      {

    scanf("%d",&d);cnt++;ans+=d;

    add(,cnt,d);add(cnt,i,INF);

    if(i!=j)add(cnt,j,INF);

      }

  cnt++;

  for(int i=,d;i<=n;i++)

    scanf("%d",&d),add(i,cnt,d);

  while(bfs())memcpy(cur,hd,sizeof hd),ans-=dinic(,INF);

  printf("%d\n",ans);

  return ;

}