题解【P7515 [省选联考 2021 A 卷] 矩阵游戏】
UperFicial
·
·
题解
P7515 [省选联考 2021 A 卷] 矩阵游戏
解题报告。
不一定更好的阅读体验。
---
一年前我在省选赛场上折戟沉沙，一年后我从倒下的地方再摔一跤。
我成功了，我仍然是以前的那个我。
----
神题，希望自己讲得清楚一些。
先不考虑 $0\le a_{i,j}\le 10^6$ 的限制，只考虑 $b_{i,j}=a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}$，瞎鸡巴填一手，得到矩阵 $A$，之后比较自然的想法就是通过 $+1$ 和 $-1$ 来微调这个东西。
其实这个时候差不多就可以想到差分约束了，因为我们最终希望把每一个 $a_{i,j}$ 变成 $0\le a_{i,j}\le 10^6$ 这样一个范围的形式。不过我知道你很急，但你先别急。继续往下做，看看这个想法有没有希望。
两个比较显然的性质：
1. 对于**每一行**轮流进行 $+1$ 和 $-1$ 的操作，结果不变。
2. 对于**每一列**轮流进行 $+1$ 和 $-1$ 的操作，结果不变。
因为任意一个 $2\times 2$ 的矩阵中的一组 $+1$ 和 $-1$ 会相互抵消掉。
我们设 $1$ 操作在第 $i$ 行进行了 $c_{i}$ 次，设 $2$ 操作在第 $j$ 行进行了 $d_i$ 次，那么可以得到如下的矩阵（每一项省略了 $a_{i,j}$）：
$$
\begin{bmatrix}
c_1+d_1 & -c_1+d_2 & \cdots & (-1)^{m+1}c_1+d_n\\
c_2-d_1 & -c_2-d_2 & \cdots & (-1)^{m+1}c_2-d_n\\
\cdots & \cdots & \ddots & \cdots\\
c_n+(-1)^{n+1}d_m & -c_n+(-1)^{n+1}d_m & \cdots & (-1)^{m+1}c_n+(-1)^{n+1}d_m
\end{bmatrix}
$$
第一眼：哇这不是差分约束板子吗！
第二眼：我是不是应该发明一个叫 $0\le a_{i,j}+c+d\le 10^6$ 的和分约束？
但是这个和分约束显然可以通过变化 $c$ 的符号来转化成差分约束。
我们将偶数行的 $c$ 变成相反数，奇数列的 $d$ 变成相反数。
那么原矩阵就变成了：
$$
\begin{bmatrix}
c_1-d_1 & d_2-c_1 & \cdots \\
d_1-c_2 & c_2-d_2 & \cdots\\
\cdots & \cdots & \ddots\\
\end{bmatrix}
$$
这里仅举例 $2\times 2$ 的矩阵已经足够证明正确性，因为包含了所有下标的奇偶性，这样的话转化就做完了。
我们先将第最后一行钦定为 $0$，然后得到了一个不考虑限制的矩阵 $A$，之后按照上面的矩阵，以 $(1,1)$ 为例，得到差分约束 $0\le a_{1,1}+c_1-d_1\le 10^6$ 的形式，跑 $\text{SPFA}$ 就行了。
注意，这道题可以不用建立虚点的，因为这张图已经保证联通了，而且是差不多是一张完全图，用链式前向星容易被卡，而 $\texttt{vector}$ 存图在稠密图的情况下是表现良好的。
证明一下这个做法的正确性，钦定 $a_{i,j}$ 会有 $(n-1)(m-1)$ 个方程，差分约束会建立 $2nm$ 个方程，但这里的方程每有两个会得到 $(n+m)$ 个未知数，每个未知数会得到一个 $a_{i,j}$，所以本质是有 $(n+m)$ 个方程，最终我们得到 $(nm+1)$ 个有关 $a$ 的方程，足以确定 $nm$ 个未知数。
个人感觉比较好看的代码：
```cpp
const int MAXN(310);
const int MAXM(610);
const int MAX(1e6);
int n,m,a[MAXN][MAXN],b[MAXN][MAXN],K;
struct node{int to,cost;};
vector<node>G[MAXM];
bool inq[MAXM];
queue<int>q;
ll d[MAXM];
int cnt[MAXM];
inline void add_edge(int u,int v,int w)
{
node res;
res.to=v,res.cost=w;
G[u].push_back(res);
return;
}
inline bool spfa(int s)
{
rep(i,1,n+m) d[i]=LLINF,inq[i]=false,cnt[i]=0;
d[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
rep(i,0,(int)G[u].size()-1)
{
node e=G[u][i];
if(d[e.to]>d[u]+e.cost)
{
d[e.to]=d[u]+e.cost;
if(!inq[e.to])
{
if(++cnt[e.to]>=n+m) return false;
inq[e.to]=true,q.push(e.to);
}
}
}
}
return true;
}
inline void solve()
{
n=Fread::read(),m=Fread::read();
rep(i,1,n-1) rep(j,1,m-1) b[i][j]=Fread::read();
rev(i,n-1,1) rev(j,m-1,1) a[i][j]=b[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1];//随便构造一个矩阵 A
rep(i,1,n) rep(j,1,m)
{
if((i+j)&1) add_edge(j+n,i,MAX-a[i][j]),add_edge(i,j+n,a[i][j]);
else add_edge(i,j+n,MAX-a[i][j]),add_edge(j+n,i,a[i][j]);
}
if(!spfa(1)) puts("NO");
else
{
puts("YES");
rep(i,1,n)
{
rep(j,1,m)
{
int now=d[i]-d[j+n];
if((i+j)&1) cout<<a[i][j]+now,putchar('\n');
else cout<<a[i][j]-now,putchar('\n');
}
putchar('\n');
}
}
Clear(a);
rep(i,1,n+m) G[i].clear();
return;
}
int main()
{
int T=Fread::read();
while(T--) solve();
return 0;
}
/*
Date : 2022/9/27
Author : UperFicial
Start coding at : 17:03
finish debugging at : 17:50
*/
```