上海大都会赛 I Matrix Game(最大流)

At the start of the matrix game, we have an N x M matrix. Each grid has some balls.
The grid in (i,j) (0 ≤ i < N, 0 ≤ j < M) has A_ij balls.
In each operation you can remove one ball from a grid or add one ball into a grid.
The goal of this game is to make each of the rows has the same number of balls and each of the columns has the same number of balls.
What is the minumun operations you should use?

输入描述:
The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.
The first line of each test case contains two integers N and M (1 ≤ N,M ≤ 20).
The next N lines describe A_ij, each line contains M integers. (0 ≤ A_ij ≤ 20).

输出描述:
For each test case, print the case number and the answer.

输入
2
2 3
4 8 5
2 4 6
3 3
1 5 2
3 5 4
2 3 4

输出
Case 1: 7
Case 2: 7

说明
for the first example, the number of balls after operations is
4 6 5
6 4 5

题意

给你一个N*M的矩阵，有两个操作，每次对1个数+1或-1，问最少操作多少次使得每行和相同，每列和相同

题解

设每行X，每列Y，可知X*N=Y*M，每一行X/N，每一列Y/M，并且lcm(N,M)|X，0<=X<=20*n*m

然后可以枚举每一个X+=lcm(N,M)，再用网络流判断

建图按行列建，S-每行流量X/N，T-每行流量Y/M，行列按a[i][j]建

跑出来最大流maxflow

+1，说明图中总共需要增加x-maxflow

-1，说明图中总共需要减掉多出来的sum-maxflow

代码

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1e5+;

 const int maxm=2e5+;

 const int INF=0x3f3f3f3f;

 int TO[maxm],CAP[maxm],NEXT[maxm],tote;

 int FIR[maxn],gap[maxn],cur[maxn],d[maxn],q[];

 int n,m,S,T;

 void add(int u,int v,int cap)

 {

     TO[tote]=v;

     CAP[tote]=cap;

     NEXT[tote]=FIR[u];

     FIR[u]=tote++;

     TO[tote]=u;

     CAP[tote]=;

     NEXT[tote]=FIR[v];

     FIR[v]=tote++;

 }

 void bfs()

 {

     memset(gap,,sizeof gap);

     memset(d,,sizeof d);

     ++gap[d[T]=];

     for(int i=;i<=n;++i)cur[i]=FIR[i];

     int head=,tail=;

     q[]=T;

     while(head<=tail)

     {

         int u=q[head++];

         for(int v=FIR[u];v!=-;v=NEXT[v])

             if(!d[TO[v]])

                 ++gap[d[TO[v]]=d[u]+],q[++tail]=TO[v];

     }

 }

 int dfs(int u,int fl)

 {

     if(u==T)return fl;

     int flow=;

     for(int &v=cur[u];v!=-;v=NEXT[v])

         if(CAP[v]&&d[u]==d[TO[v]]+)

         {

             int Min=dfs(TO[v],min(fl,CAP[v]));

             flow+=Min,fl-=Min,CAP[v]-=Min,CAP[v^]+=Min;

             if(!fl)return flow;

         }

     if(!(--gap[d[u]]))d[S]=n+;

     ++gap[++d[u]],cur[u]=FIR[u];

     return flow;

 }

 int ISAP()

 {

     bfs();

     int ret=;

     while(d[S]<=n)ret+=dfs(S,INF);

     return ret;

 }

 void init()

 {

     tote=;

     memset(FIR,-,sizeof FIR);

 }

 int main()

 {

     int t,N,M,ca=;

     int a[][];

     scanf("%d",&t);

     while(t--)

     {

         int sum=;

         scanf("%d%d",&N,&M);

         for(int i=;i<=N;i++)

             for(int j=;j<=M;j++)

                 scanf("%d",&a[i][j]),sum+=a[i][j];

         int up=N/__gcd(N,M)*M;

         int minn=1e9;

         S=N+M+,T=S+,n=T;

         for(int x=;x<=*N*M;x+=up)

         {

             init();

             for(int i=;i<=N;i++)add(S,i,x/N);

             for(int i=;i<=M;i++)add(N+i,T,x/M);

             for(int i=;i<=N;i++)

                 for(int j=;j<=M;j++)

                     add(i,N+j,a[i][j]);

             minn=min(minn,x+sum-ISAP()*);

         }

         printf("Case %d: %d\n",ca++,minn);

     }

     return ;

 }

巴特西

上海大都会赛 I Matrix Game(最大流)

最新文章

热门文章