题解：P4578 [FJOI2018] 所罗门王的宝藏

chinazhanghaoxun · 2025-11-28 21:47:40 · 题解

P4578 [FJOI2018] 所罗门王的宝藏 - 题解

前置知识

本题思路是将等式转化为两个不等式，进而使用差分约束算法，建议先复习一下 P5960 【模板】差分约束。

题意

给定一个二维矩阵，矩阵中每个元素初始都是 0。每次操作指定一行或一列，可以让对应行或列的元素都 +1，或都 −1。矩阵中有一些位置为给定的密码元素，只有矩阵中所有的密码元素都正确，锁才会打开，问是否可能将锁打开。

分析

假设第 i 行的数值被增加了 u_i 次，第 j 行的数值被增加了 v_j 次，位置为 (i,j) 的密码值为 w_{i,j}，可以得到 u_i+v_j=w_{i,j}，此时使用差分约束，可以得到两个不等式：

但是由于这里均为加法，不好处理，于是改变定义，设第 j 行的数值被减小了 v_j 次，此时才得到了 u_i-v_j=w_{i,j}，转化为：

移项并整理，得到：

连边时要注意点的编号之间不冲突，不妨令 j\gets j+n，于是可以建图，j+n\xrightarrow{w}i，i\xrightarrow{-w}j+n。

由于题目仅查询是否存在解，只需判断图中是否有负环，使用 SPFA 即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=4005;
int T,n,m,k,cnt[N],dis[N]; //注意存在j+n，所以要开两倍空间
bool vis[N];
vector<pair<int,int>> e[N];

bool spfa(int s){
    queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto i:e[u]){
            int v=i.first,w=i.second;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    cnt[v]++;
                    if(cnt[v]==n+m+1) return false; //这个点入队次数超过总点数，说明存在负环 
                    q.push(v);
                }
            }
        }
    }
    return true;
}

void init(){
    e[0].clear();
    for(int i=1;i<=n+m+1;i++){
        e[i].clear();
        e[0].push_back({i,0}); //设置超级源点 
        vis[i]=0;
        cnt[i]=0;
    }
}

int main(){
    cin>>T;
    while(T--){
        cin>>n>>m>>k;
        init(); //多测清空，注意SPFA中涉及的变量也要清空 
        for(int i=1;i<=k;i++){
            int x,y,z;
            cin>>x>>y>>z;
            e[y+n].push_back({x,z}); //使用差分约束算法建边 
            e[x].push_back({y+n,-z});
        }
        if(spfa(0)) puts("Yes"); //从超级源点开始判断，保证图联通 
        else puts("No");
    }
    return 0;
}