CF1913E费用流

Posted on Edited on

题目链接 # 题意

给出一个 \(n\times m\) 的 0/1 矩阵，可以反转若干个位置，再给出 \(A_n,B_m\)，要求最终第 \(i\) 行恰有 \(A_i\) 个 \(1\)，第 \(j\) 列恰有 \(B_j\) 个 \(1\)，问最少需要反转多少个位置，无解输出 -1。\(n,m\le 50\)。

分析

很自然可以想到网络流来模拟是否对矩阵反转，我的方法如下：

每行，每列都加一个哨兵节点，源点向每个行哨兵节点连边，流量限制为 \(A_i\),行哨兵节点再向矩阵的每个点连边，流量限制为\(1\)，矩阵的每个点再向列哨兵节点连边，流量为\(1\),每个列哨兵节点再向汇点连边，流量为\(B_j\)。

现在考虑如何衡量操作次数，在行哨兵向矩阵节点连边时，如果 \(a_{i,j}=1\),那么设定费用为 \(-1\),反之设定为\(1\),最后只要判断最大流是否等于 \(\sum A_i\),\(\sum A_i=\sum B_j\),答案为\(cst+\sum a_{i,j}\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define dow(i,j,k) for(i=j;i>=k;--i)
const int N=70;
struct edge{
    int nxt,to,w,c;
}e[(N*N)*3];
int head[N*N],pos,s,t,dis[N*N],pre[N*N],ep[N*N],flow,cst;
bool vis[N*N];
void add(int u,int v,int w,int c){
    e[++pos]=(edge){head[u],v,w,c};head[u]=pos;
}
bool spfa(){
    int i;rep(i,1,t)dis[i]=1<<30;
    queue<int>q;
    memset(vis,0,sizeof(vis));
    rep(i,1,t)pre[i]=-1;
    dis[s]=0;vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(i=head[u];i;i=e[i].nxt)if(e[i].w>0 && dis[e[i].to]>dis[u]+e[i].c){
                dis[e[i].to]=dis[u]+e[i].c;ep[e[i].to]=i;
                pre[e[i].to]=u;if(!vis[e[i].to])q.push(e[i].to);vis[e[i].to]=1;
            }
    }
    return dis[t]<(1<<30);
}
void EK(){
    int i;
    while(spfa()){
        int f=1<<30;
        for(i=t;i!=s;i=pre[i])
            f=min(f,e[ep[i]].w);
        flow+=f;cst+=f*dis[t];
        for(i=t;i!=s;i=pre[i])e[ep[i]].w-=f,e[ep[i]^1].w+=f;
    }
}
int n,m,a[N][N],A[N],B[N];
void eg(int u,int v,int w,int c){
    add(u,v,w,c);add(v,u,0,-c);
}
int main(){//freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m;int i,j;
    rep(i,1,n)rep(j,1,m)cin>>a[i][j];
    rep(i,1,n)cin>>A[i];rep(i,1,m)cin>>B[i];
    int ps=n*m+n+m;pos=1;
    s=++ps;t=++ps;
    int con=0,slc[2]={1,-1};
    rep(i,1,n)rep(j,1,m){
        eg(n*m+i,(i-1)*m+j,1,slc[a[i][j]]);
        eg((i-1)*m+j,n*m+n+j,1,0);
        con+=a[i][j];
    }
    rep(i,1,n){
        eg(s,n*m+i,A[i],0);
    }
    rep(j,1,m)eg(n*m+n+j,t,B[j],0);
    int sa,sb;sa=sb=0;
    rep(i,1,n)sa+=A[i];rep(j,1,m)sb+=B[j];
    EK();
    if(sa==sb && sa==flow)cout<<cst+con;else cout<<-1;
}