自动搬运

查看原文

来自洛谷，原作者为

	未见堇开 是环境在影响着我。

搬运于2025-08-24 22:01:35，当前版本为作者最后更新于2019-03-20 22:03:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

差分约束做法。

设第$r$行的操作使这一行的数增加了$x_{r}$，第$c$列的操作使这一列的数减少了$y_{c}$，

那么显然对于第$r$行第$c$列绿宝石的密码$p$，有$x_{r}-y_{c}=p$

即：$\left\{\begin{matrix}x_{r}-y_{c}\leq p\\x_{r}-y_{c}\geq p\end{matrix}\right.$

移项得$\left\{\begin{matrix}x_{r}-y_{c}\leq p\\y_{c}-x_{r}\leq -p\end{matrix}\right.$

对两个不等式分别连边$(r\overset {p}{\rightarrow}c+n)\; ,\; (c+n\overset {-p}{\rightarrow}r)$，即可构造差分约束系统。

因为题目只求解的存在性，判负环即可。

讲解到此为止。放代码。

#include<cstdio>
#include<queue>
#define reg register
#define MAXN 2019
using namespace std;

struct edge
{int pre,dis,to;}e[5005];
int n,m,k,s,ptr_e;
bool have=false;
int last[MAXN],dis[MAXN],inq[MAXN],vis[MAXN];

inline void spfa()
{
	dis[s]=0;
	queue<int> q; 
	for(int i=1;i<=n+m;i++)
		dis[i]=0x23333333,inq[i]=vis[i]=0;
	q.push(s),vis[s]=1;
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop(),inq[tmp]=0;
		for(reg int i=last[tmp];i;i=e[i].pre)
		{
			int v=e[i].to,w=e[i].dis;
			if(dis[v]>dis[tmp]+w)
			{
				if(vis[v]>=n+m)
				{
					have=true;
					return;
				}
				dis[v]=dis[tmp]+w;
				if(!inq[v])
				{
					++vis[v],inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	have=false;
	return;
}

inline void addedge(int u,int v,int d)//连边
{
	e[++ptr_e].pre=last[u];
	e[ptr_e].dis=d,e[ptr_e].to=v,last[u]=ptr_e;
	return;
}

inline int qin()//快读
{
	reg int ans=0,m=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			m=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		ans=ans*10+(ch-'0');
		ch=getchar();
	}
	return(ans*m);
}

int main()
{
	int t=qin();
	while(t--)
	{
		n=qin(),m=qin(),k=qin();
		ptr_e=0,s=n+m+1;
		last[s]=0;
		for(reg int i=1;i<=n+m;i++)
			last[i]=0,addedge(s,i,0);
		while(k--)
		{
			int u=qin(),v=qin(),d=qin();
			addedge(u,v+n,d),addedge(n+v,u,-d);
		}
		spfa();
		if(have)
			puts("No");
		else
			puts("Yes");
	}
	return(0);
}

97msAC