题目:
Description
有一个n*m的矩阵，初始每个格子的权值都为0，可以对矩阵执行两种操作：
- 选择一行， 该行每个格子的权值加1或减1。
- 选择一列， 该列每个格子的权值加1或减1。 现在有K个限制，每个限制为一个三元组(x,y,c)，代表格子(x,y)权值等于c。 问是否存在一个操作序列，使得操作完后的矩阵满足所有的限制。如果存在输出”Yes”，否则输出”No”。
题解:
如果我们将所有的行作为变量\(x\),所有的列作为变量\(y\).
变量本身代表对这行(列)进行的操作数(x,y可以为负) 所以对于每一个三元限制我们可以列出方程\(x_i + y_i = c_i\) 然后我们移项得到\(x_i - c_i = y_i\) 这样我们可以依据这个等式列出两个不等式:- $ x_i - c_i \leq y_i $
- $ y_i - (-c_i) \leq x_i $
然后我们建立差分约束系统,dfs判正环即可.
#include#include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}const int maxn = 2048;const int maxm = 1024*1024;struct Edge{ int to,next,dis;}G[maxm];int head[maxn],cnt;void add(int u,int v,int d){ G[++cnt].to = v; G[cnt].next = head[u]; head[u] = cnt; G[cnt].dis = d;}int dis[maxn];bool inq[maxn];inline void init(){ memset(head,0,sizeof head); memset(dis,-0x3f,sizeof dis); memset(inq,false,sizeof inq); cnt = 0;}#define v G[i].tobool dfs(int u){ inq[u] = true; for(int i = head[u];i;i=G[i].next){ if(dis[v] < dis[u] + G[i].dis){ dis[v] = dis[u] + G[i].dis; if(inq[v]) return false; if(!dfs(v)) return false; } } inq[u] = false; return true;}#undef vint x[maxn],y[maxn],c[maxn];int work(){ init(); int n,m,k;read(n);read(m);read(k); for(int i=1;i<=k;++i) read(x[i]),read(y[i]),read(c[i]); for(int i=1;i<=k;++i){ for(int j=1;j<=k;++j){ if(x[i] == x[j] && y[i] == y[j] && c[i] != c[j]) return puts("No"); if(x[i] == x[j] && y[i] == y[j]) continue; if(x[i] == x[j] && c[i] - c[j] >= 0){ add(y[j]+n,y[i]+n,c[i]-c[j]); add(y[i]+n,y[j]+n,c[j]-c[i]); } if(y[i] == y[j] && c[i] - c[j] >= 0){ add(x[j],x[i],c[i]-c[j]); add(x[i],x[j],c[j]-c[i]); } } } for(int i=1;i<=n+m;++i) if(!dfs(i)) return puts("No"); return puts("Yes");}int main(){ int T;read(T); while(T--) work(); getchar();getchar(); return 0;}