Link:https://www.lydsy.com/JudgeOnline/problem.php?id=2756
Algorithm:
比较新颖的题目
首先发现是对矩阵中相邻两数进行操作 <-----> 想到黑白染色
于是Delta(BlackSum)=Delta(WhiteSum)
由于最后要变成同一个数X，
那么在BlackNum=WhiteNum时，
1、如果WhiteSum！=BlackSum，显然无解
2、如果WhiteSum==BlackSum时，由于矩阵能被1*2的矩形完全覆盖，那么X是否满足要求是具有单调性的
于是我们二分X，进行判断即可
在WhiteNum!=BlackNum时，
显然可以得到X∗WhiteNum−WhiteSum=X∗BlackNum−BlackSum
移项后显然可以化简出X=（BlackSum−WhiteSum） / （BlackNum−WhiteNum）
验证这个X即可
最大问题，如何判断X是否可行，
一开始得出的性质：Delta(BlackSum)=Delta(WhiteSum)，符合流守恒性（流入和流出量相同）
于是我们进行可以将黑点看作一边，而将白点看作另外一边，网络流建图：
S-->白点，CAP为X-val[i][j]
黑点-->T，CAP为X-val[i][j]
相邻的白点-->黑点，CAP为INF
判断能否满流即可
Code:
#include <bits/stdc++.h> using namespace std;
#define pos(x,y) (x-1)*m+y
typedef pair<int,int> P;
typedef long long ll;
const int MAXN=;
const ll INF=1ll<<; ll test,n,m,col[MAXN][MAXN],dat[MAXN][MAXN],iter[MAXN*MAXN],level[MAXN*MAXN];
ll sum1,sum2,cnt1,cnt2,mx,S,T; struct edge
{
ll to,cap,rev;
};
vector<edge> G[MAXN*MAXN]; void add_edge(int from,int to,ll cap)
{
G[from].push_back(edge{to,cap,G[to].size()});
G[to].push_back(edge{from,,G[from].size()-});
} bool bfs()
{
memset(level,-,sizeof(level));
queue<int> que;que.push(S); level[S]=;
while(!que.empty())
{
int t=que.front();que.pop();
for(int i=;i<G[t].size();i++)
{
edge e=G[t][i];
if(e.cap> && level[e.to]==-)
{
level[e.to]=level[t]+;
que.push(e.to);
}
}
}
} ll dfs(int cur,int T,ll f)
{
if(cur==T) return f; for(ll &i=iter[cur];i<G[cur].size();i++)
{
edge &e=G[cur][i];
if(level[e.to]==level[cur]+ && e.cap>)
{
ll d=dfs(e.to,T,min(f,e.cap));
if(d>)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return ;
} ll dinic()
{
ll ret=;
while(true)
{
memset(iter,,sizeof(iter));
bfs();if(level[T]==-) break;
ll f;
while((f=dfs(S,T,INF))>) ret+=f; //这里括号不能排错啊
}
return ret;
} int dx[]={,,,-};
int dy[]={,-,,}; bool check(ll tar)
{
S=;T=n*m+;ll ret=;
for(int i=;i<MAXN*MAXN;i++) G[i].clear();
for(int i=;i<=n;i++) //建图
for(int j=;j<=m;j++)
{
if(col[i][j]) add_edge(S,pos(i,j),tar-dat[i][j]),ret+=tar-dat[i][j];
else {add_edge(pos(i,j),T,tar-dat[i][j]);continue;}
for(int k=;k<;k++)
{
int fx=i+dx[k],fy=j+dy[k];
if(fx>= && fx<=n && fy>= && fy<=m)
add_edge(pos(i,j),pos(fx,fy),INF);
}
} ll MAXFLOW=dinic(); //dinic
return (ret==MAXFLOW);
} int main()
{
cin >> test;
while(test--)
{
cin >> n >> m;mx=;
cnt1=cnt2=sum1=sum2=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
cin >> dat[i][j];
col[i][j]=(i+j)&;mx=max(mx,dat[i][j]);
if(col[i][j]) sum1+=dat[i][j],cnt1++;
else sum2+=dat[i][j],cnt2++;
} if(cnt1!=cnt2)
{
ll tar=(sum1-sum2)/(cnt1-cnt2);
if(tar<mx){puts("-1");continue;} if(check(tar))
{
cout << tar*cnt1-sum1 << endl;
continue;
}
puts("-1");
}
else
{
if(sum1!=sum2){puts("-1");continue;} ll l=mx,r=INF;
while(l<=r)
{
ll mid=(l+r)>>;
if(check(mid)) r=mid-;
else l=mid+;
}
if(r==INF) puts("-1"); //如果到INF都无解，则说明就是无解，要特判，但BZOJ上数据比较水（黄学长的标程是错的）
else cout << 1ll*(l*cnt1-sum1) << endl;
}
}
return ;
}
Review:
1、看到这种对相邻格子同时操作的题目，想到黑白染色
2、求极值，观察值的可行性是否具有单调性，从而能否二分
3、当数据能分为两组，且具有流守恒性时
考虑使用网络流
4、调试：
（1）有多个括号要留心每个括号的位置啊，多看几遍
while((f=dfs(S,T,INF))>)
这里的>0一开始放到第2个括号里了，结果f每次就都是0或1了……囧，调了1h
（2）像网络流这样执行过一边就会对原数组产生影响的模块，
执行过一次后想调试/再次调用时，不能再执行一遍，将第一次结果存储即可
（3）由于模板中大部分数据都是int，如果有long long时要特别注意修改原模板中的int
*：
void add_edge(int from,int to,ll cap)