[HDOJ3666 Regional Harbin THE MATRIX PROBLEM]【差分约束系统变形】

【题目大意】
给定一个矩阵C[i][j],每行数都乘一个a[i],每列数都除以一个b[i],然后使得矩阵里每个数都L<=x<=U。
问是否存在这样的a[i],b[i]。
【算法分析】
易得不等式
(a[i]/b[i])*C[i][j]>=L
(a[i]/b[i])*C[i][j]<=U
移项
a[i]*(C[i][j]/L)>=b[i]
b[i]*(U/C[i][j])>=a[i]
那么我们建边
然后用最短路松弛之。其实就是差分约束系统了。。。
【其它】
由于顺序问题。。。我把入栈限制限为2居然过了。。。
【CODE】
http://xiudaima.appspot.com/code/detail/1615006

加入对话

4条评论

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注