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

前置知识

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

题意

给定一个二维矩阵，矩阵中每个元素初始都是

0

。每次操作指定一行或一列，可以让对应行或列的元素都

+1

，或都

−1

。矩阵中有一些位置为给定的密码元素，只有矩阵中所有的密码元素都正确，锁才会打开，问是否可能将锁打开。

分析

假设第

i

行的数值被增加了

u_i

次，第

j

行的数值被增加了

v_j

次，位置为

(i,j)

的密码值为

w_{i,j}

，可以得到

u_i+v_j=w_{i,j}

，此时使用差分约束，可以得到两个不等式：

\begin{cases} u_i+v_j\le w_{i,j}\\ u_i+v_j\ge w_{i,j} \end{cases}

但是由于这里均为加法，不好处理，于是改变定义，设第

j

行的数值被减小了

v_j

次，此时才得到了

u_i-v_j=w_{i,j}

，转化为：

\begin{cases} u_i-v_j\le w_{i,j}\\ u_i-v_j\ge w_{i,j} \end{cases}

移项并整理，得到：

\begin{cases} u_i-v_j\le w_{i,j}\\ v_j-u_i\le -w_{i,j} \end{cases}

连边时要注意点的编号之间不冲突，不妨令

j\gets j+n

，于是可以建图，

j+n\xrightarrow{w}i

，

i\xrightarrow{-w}j+n

。

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

代码

CPP

#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;
}

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

文章操作

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

前置知识

题意

分析

代码

相关推荐

评论

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