bzoj 3996 线性代数 —— 最大权闭合子图

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

把题中的式子拆开看看，发现就是如下关系：

如果 a[i] == 1 && a[j] == 1，则 b[i][j] 有贡献；

如果 a[i] == 1，则 -c[i] 有贡献；

所以就是最大权闭合子图的模型，b[i][j] 向 a[i] 和 a[j] 连边，a[i] 向 c[i] 连边；

而 c[i] 这个点实际上没什么用，直接变成 a[i] 向 T 连边，边权是 c[i] 即可。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const xn=,xm=(xn<<),inf=0x3f3f3f3f;

int n,hd[xn],ct,to[xm],nxt[xm],c[xm],S,T,dis[xn],cur[xn];

queue<int>q;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void ade(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;}

void add(int x,int y,int z){ade(x,y,z); ade(y,x,);}

bool bfs()

{

  while(q.size())q.pop();

  memset(dis,,sizeof dis);

  dis[]=; q.push();

  while(q.size())

    {

      int x=q.front(); q.pop();

      for(int i=hd[x],u;i;i=nxt[i])

    if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);

    }

  return dis[T];

}

int dfs(int x,int fl)

{

  if(x==T)return fl;

  int ret=;

  for(int &i=cur[x],u;i;i=nxt[i])

    {

      if(dis[u=to[i]]!=dis[x]+||!c[i])continue;

      int tmp=dfs(u,min(fl-ret,c[i]));

      if(!tmp)dis[u]=;

      c[i]-=tmp; c[i^]+=tmp;

      ret+=tmp; if(ret==fl)break;

    }

  return ret;

}

int main()

{

  n=rd(); S=; T=n*n+n+; int ans=;

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

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

      {

    x=rd(); cnt++; ans+=x;

    add(S,cnt,x);

    add(cnt,n*n+i,inf); add(cnt,n*n+j,inf);

      }

  for(int i=,x;i<=n;i++)x=rd(),add(n*n+i,T,x);

  while(bfs())

    {

      memcpy(cur,hd,sizeof hd);

      ans-=dfs(S,inf);

    }

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

  return ;

}