之前居然不知道矩阵的转置是什么/qd，百度一下发现这就是把矩阵的横竖颠倒一下。

然后进行一个柿子的推，发现 $D=\sum\limits_{i=1}^n a_i\ (\sum\limits_{j=1}^na_j\times b_{j,i}-c_i)$，由于 $c_i$ 这个东西的存在，且 $a$ 是 $01$ 矩阵，所以考虑最小割。

令 $a_i=1$ 的点 $i$ 属于集合 $S$，$a_i=0$ 的点 $i$ 属于集合 $T$，套路性地把每个点 $i$ 拆成横竖两个点 $x_i$ 和 $y_i$，根据式子建图：

• $a_i=0$ 损失的贡献为 $sum_i=\sum\limits_{j=1}^n b_{j,i}$，可以表示为连边 $(s,x_i,sum_i)$；
• $a_i=1$ 且 $a_j=0$ 损失的贡献为 $b_{j,i}$，表示为连边 $(x_i,y_j,b_{j,i})\ (j\ne i)$，$i=j$ 时不可能出现这种情况，即连边 $(x_i,y_i,+\infty)$；
• $a_i=1$ 要额外损失贡献 $c_i$，即连边 $(y_i,t,c_i)$，当 $i\in S$ 时强制切断这条边。

跑 Dinic 即可，答案即 $ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^n b_{i,j}-$ 最小割。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,s,e) for(int i=(s);i<=(e);++i)
#define Rep(i,s,e) for(int i=(e);i>=(s);--i)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=1010,M=1e6+5;
int n,s,t,b[N>>1][N>>1],c[N],sum[N];
int head[N],rad[N],cnt=1;
struct qwq{
    int v,w,nxt;
}e[M];
inline void add(int u,int v,int w){
    e[++cnt]={v,w,head[u]},head[u]=cnt;
    e[++cnt]={u,0,head[v]},head[v]=cnt;
}
int dep[N];
inline bool bfs(){
    queue<int> q;
    rep(i,1,t) dep[i]=0;
    dep[s]=1,q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        rad[x]=head[x];
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(w&&!dep[v]) dep[v]=dep[x]+1,q.push(v);
        }
    }
    return dep[t]!=0;
}
int dfs(int x,int flow){
    if(x==t) return flow;
    int out=0;
    for(int &i=rad[x];i;i=e[i].nxt){
        int v=e[i].v,&w=e[i].w;
        if(w&&dep[v]==dep[x]+1){
            int res=dfs(v,min(flow,w));
            out+=res,flow-=res,w-=res,e[i^1].w+=res;
        }
        if(!flow) break;
    }
    if(flow) dep[x]=-1;
    return out;
}
signed main(){
    n=read(),s=n<<1|1,t=s+1;
    int ans=0,tmp;
    rep(i,1,n) rep(j,1,n) b[i][j]=read(),sum[j]+=b[i][j];
    rep(i,1,n) c[i]=read(),ans+=sum[i];
    rep(i,1,n){
        add(s,i,sum[i]),add(i+n,t,c[i]),add(i,i+n,1e9);
        rep(j,1,n) if(j!=i) add(i,j+n,b[j][i]);
    }
    while(bfs()) while(tmp=dfs(s,1e9)) ans-=tmp;
    // rep(i,1,t) cerr<<dep[i]<<' ';cerr<<endl;
    printf("%d\n",ans);
}