Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

05/29
08:25
dfs

[bzoj 4500] 矩阵

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有一个n*m的矩阵,初始每个格子的权值都为0,可以对矩阵执行两种操作:
1. 选择一行, 该行每个格子的权值加1或减1。
2. 选择一列, 该列每个格子的权值加1或减1。
现在有K个限制,每个限制为一个三元组(x,y,c),代表格子(x,y)权值等于c。问是否存在一个操作序列,使得操作完后的矩阵满足所有的限制。如果存在输出”Yes”,否则输出”No”。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

先输入一个T(T <= 5)代表输入有T组数据,每组数据格式为:
第一行三个整数n, m, k (1 <= n, m,k <= 1000)。
接下来k行,每行三个整数x, y, c。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每组数据,输出Yes或者No。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 1

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

Yes
No

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

设x[i]为第i行最后的贡献,y[i]为第i列最终的贡献
对于一个限制条件x,y,c,显然要满足x[i]+y[i]=c,所以可以从x[i]向y[i]连一条边权为c的边.
把初始权值赋成随意什么数,暴力dfs一遍就可以了.
c++:
pascal:

[bzoj 4500] 矩阵