题目描述：

给你一个N*M的矩阵，给你两个数L和U（L <= U）问你是否存在这样的N+M个数字（计作A1….AN, B1…..BM），使矩阵中任意元素Xij，满足：

L <= (Xij * Ai) / Bj <= U

输出YES OR NO。

解题报告：

转换成：Xij * Ai – U * Bj <= 0 和 L*Bj – Xij * Ai <= 0

差分约束中的xi – xj <= val, 中的xi和xj都不能够有系数。

那么有了系数，只需去log把乘法转化成加法就好了：

Log(Xij) + logAi – LogU – LogBj <= 0 è logAi – LogBj <= LogBj – LogXij

另一个式子也同理，这样就转化成了标准的差分约束。

注意：

判断有无解（负环）的时候，如果用spfa，不能用入队次数大于N来判断，会超时。

有如下两种比较可靠的方法（一般情况下）

1：某个点入队次数大于sqrt(N)的时候

2：所有入队次数大于T * （N + M），其中T一般取2

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define size 100000
int n, m;
double u, l;
struct edge{int from, to, next; double val;} e[400 * 400 * 10];
int cnt, v[1000], num[1000];
bool vst[1000];
void insert(int from, int to, double val)
{
    e[cnt].from = from, e[cnt].val = val;
    e[cnt].next = v[from];
    e[cnt].to = to; v[from] = cnt++;
}
double d[1000];
bool spfa(int lar)
{
    for(int i = 0; i < lar; i++) vst[i] = 0, d[i] = 10000000, num[i] = 0;
    d[0] = 0;queue<int> que;
    vst[0] = 1; que.push(0);int sum = 0;
    while(!que.empty())
    {
        int id = que.front(); vst[id] = 0;
        que.pop();
        for(int i = v[id]; i != -1; i = e[i].next)
            if (d[id] + e[i].val < d[e[i].to])
            {
                d[e[i].to] = d[id] + e[i].val;
                if (!vst[e[i].to])
                {
                    vst[e[i].to] = 1;
                    que.push(e[i].to);
                    sum++;
                    if (sum > 2 * (lar + 2 * m)) return 0;
                }
            }
    }
    return true;
}
int main()
{
    while(scanf("%d%d%lf%lf", &n, &m, &l, &u) != EOF)
    {
        cnt = 0;memset(v, -1, sizeof(int) * (n + m + 2));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
                int tmp;
                scanf("%d", &tmp);
                insert(i, n + j, -log(l/tmp));
                insert(n + j, i, log(u/tmp));
            }
        if (spfa(n + m))
            printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}