题目
题解
把题目中给的式子拆开后得到：$\sum_{i=1}^{n}\sum_{j=1}^{n}A_jB_{j,i}A_i-\sum_{i=1}^nA_iC_i$
注意到$A$只有$0/1$两种取值，所以可以看成选了$B_{j,i}$之后必须选$-C_i,-C_j$，把代表$B_{j,i}$的点向代表$-C_i,-C_j$的点连边，这样就转化成了一个最大权闭合子图问题了，最小割解决即可
边数有$1.5e6$条……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=3e5+5,N=5e2+5,inf=1e9;
struct p{
int x,y,d;
}c[MAX*6];
int n,m,num=1,cnt,T,ans;
int h[MAX],H[MAX],qu[MAX],d[MAX];
int B[N][N];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
bool bfs()
{
memset(d,0,sizeof(d));
int hl=1,tl=d[0]=1;
while(hl<=tl)
{
int tt=qu[hl++];
for(int i=h[tt],y;i;i=c[i].x)
if(c[i].d&&!d[y=c[i].y])
{
d[y]=d[tt]+1,qu[++tl]=y;
if(y==T) return 1;
}
}
return 0;
}
int dfs(int x=0,int dix=inf)
{
if(!dix||x==T) return dix;
int sum=0;
for(int &i=H[x],dis,y;i;i=c[i].x)
if(d[y=c[i].y]==d[x]+1&&c[i].d)
{
dis=dfs(y,min(dix,c[i].d));
if(dis)
{
sum+=dis,dix-=dis,c[i].d-=dis,c[i^1].d+=dis;
if(!dix) break;
}
}
if(!sum) d[x]=-2;
return sum;
}
int Dinic()
{
int tot=0,D;
while(bfs())
{
memcpy(H,h,sizeof(h));
while(D=dfs()) tot+=D;
}
return tot;
}
void add(int x,int y,int d)
{
c[++num]=(p){h[x],y,d},h[x]=num;
c[++num]=(p){h[y],x,0},h[y]=num;
}
int main()
{
n=read(),cnt=2*n,T=cnt+n*n+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
ans+=(B[i][j]=read()),add(i,++cnt,inf),add(j,cnt,inf),add(cnt,T,B[i][j]);
for(int i=1;i<=n;++i)
add(0,i,read());
return printf("%d",ans-Dinic()),0;
}
