题解 P7515【[省选联考 2021 A 卷] 矩阵游戏】

· · 题解

P7515 [省选联考 2021 A 卷] 矩阵游戏解题报告：

更好的阅读体验

题意

给定大小为(n-1)\times(m-1)的矩阵b，求生成任意一个满足条件的a满足：

保证0\leqslant b_{i,j}\leqslant 4\times 10^6，2\leqslant n,m\leqslant 300。

分析

可能是暗中送我退役的一道题，我要是把这个思路想下去做掉这道题，那我剩下的题用头打都能进队啊！！！！！！！！！！！！！！！！！！！！！！！！！！！！

技不如人，肝败吓疯。

首先不考虑0\leqslant a_{i,j}\leqslant 10^6，并钦定a_{i,1}=a_{1,j}=0，不难发现可以生成一组解a'。

我们考虑通过调整某些位置的权值使得最后的解权值满足限制。

发现对某一行交替+r,-r,+r,-r\cdots后的解仍然满足矩阵b的限制；同理，对某一列交替+c,-c,+c,-c\cdots后的解也仍然满足矩阵b的限制。

不难发现任意一组解都可以被这样表示出来：

\begin{bmatrix}a'_{1,1}+r_1+c_1&a'_{1,2}-r_1+c_2&a'_{1,3}+r_1+c_3&\cdots\\a'_{2,1}+r_2-c_1& a'_{2,2}-r_2-c_2& a'_{2,3}+r_2-c_3&\cdots\\a'_{3,1}+r_3+c_1& a'_{3,2}-r_3+c_2&a'_{3,3}+r_3+c_3&\cdots\\\vdots&\vdots&\vdots&\ddots\end{bmatrix}

再考虑0\leqslant a_{i,j}\leqslant 10^6这一限制，不难发现把c序列与r序列看做未知量之后可以对其进行差分约束。

但是对于同号的不等式是很难进行差分约束的，考虑定义c'_{k}=\begin{cases}-c_k&k\equiv 1\pmod 2\\c_k&k\equiv 0\pmod 2\end{cases},r'_{k}=\begin{cases}r_k&k\equiv 1\pmod 2\\-r_k&k\equiv 0\pmod 2\end{cases}

然后再次带入上面的解可以得到一个很优美的形式：

\begin{bmatrix}a'_{1,1}+r'_1-c'_1&a'_{1,2}-r'_1+c'_2&a'_{1,3}+r'_1-c'_3&\cdots\\a'_{2,1}-r'_2+c'_1& a'_{2,2}+r'_2-c'_2& a'_{2,3}-r'_2+c'_3&\cdots\\a'_{3,1}+r'_3-c'_1& a'_{3,2}-r'_3+c'_2&a'_{3,3}+r'_3-c'_3&\cdots\\\vdots&\vdots&\vdots&\ddots\end{bmatrix}

这样就可以进行差分约束了，复杂度：O((n+m)nm)。

代码

Bellman Ford被卡常了（需要特判才能过），迫不得已用了spfa/kk

#include<stdio.h>
#include<queue>
#include<vector>
#define inf 10000000000000000
using namespace std;
const int maxn=305,maxm=maxn*maxn*2;
int T,n,m,e;
int a[maxn][maxn],b[maxn][maxn],vis[maxn<<1],tot[maxn<<1];
vector<int>v[maxn<<1],w[maxn<<1];
long long dis[maxn<<1];
queue<int>q;
inline void add(int x,int y,int z){
    v[x].push_back(y),w[x].push_back(z);
}
inline void limit(int x,int y,int v){
    add(x,y,v);//v+x-y>=0
    add(y,x,1000000-v);//v+x-y<=1000000
}
int spfa(){
    while(!q.empty())
        q.pop();
    for(int i=1;i<=n+m;i++)
        dis[i]=inf,tot[i]=0,vis[i]=0;
    dis[1]=0,vis[1]=1,q.push(1);
    while(!q.empty()){
        int x=q.front();
        tot[x]++;
        if(tot[x]>n+m)
            return 1;
        q.pop();
        for(int i=0;i<v[x].size();i++){
            int y=v[x][i],z=w[x][i];
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;
                if(vis[y]==0)
                    vis[y]=1,q.push(y);
            }
        }
        vis[x]=0;
    }
    return 0;
}
inline int calc(int x,int y){
    return a[x][y]+(int)(((x+y)&1)? (dis[n+y]-dis[x]):(dis[x]-dis[n+y]));
}
int main(){
    scanf("%d",&T);
    while(T--){
        e=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                scanf("%d",&b[i][j]);
        for(int i=2;i<=n;i++)
            for(int j=2;j<=m;j++)
                a[i][j]=b[i-1][j-1]-a[i-1][j-1]-a[i-1][j]-a[i][j-1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if((i+j)&1)
                    limit(n+j,i,a[i][j]);
                else limit(i,n+j,a[i][j]);
            }
        if(spfa()){
            puts("NO");
            for(int i=1;i<=n+m;i++)
                v[i].clear(),w[i].clear();
            continue;
        }
        puts("YES");
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%d%c",calc(i,j),j==m? '\n':' '),a[i][j]=0;
        for(int i=1;i<=n+m;i++)
            v[i].clear(),w[i].clear();
    }
    return 0;
}

省选联考A卷全部题解可见：2021省选联考A卷解题报告