P3973 [TJOI2015]线性代数 题解

· · 题解

之前居然不知道矩阵的转置是什么/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，根据式子建图：

跑 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);
}