题目链接：https://cn.vjudge.net/contest/276233#problem/H

题目大意：对于给定的矩阵  每一行除以ai  每一列除以bi 之后 数组的所有元素都还在那个L-R范围之内，a[i]和b[j]是不知道的，然后问你是否有这样的数组a和数组b满足条件。

具体思路：我们可以写出这样的等式，

L<=Map[i][j]*a[i]/b[j]<=R,

然后继续化简 L/Map[i][j]<=a[i]/b[j]<=R/Map[i][j]，

然后两边同时取log，就变成了 log（L/Map[i][j]）<=log(a[i])-log(b[j])<=log(R/Map[i][j])。

然后我们就可以建边了，把log（a[i])和log(b[j])分别看成点（因为建边只考虑起点，终点，权值，而对于这个式子，边权是知道的，起点和终点可以抽象成点），然后通过差分建边就可以了，判断有没有负环，如果有负环，就代表没有可行解，否则就代表有可行解。

这个题还需要有一个优化，在判断负环的时候，我们可以直接判断他的入队列次数是不是大于sqrt（n+m），如果大于就肯定存在负环（这个好像不太稳定，以后如果这种题超时实在改不了的话，可以尝试一下这个优化）。

AC代码：

#include<iostream>

#include<cstring>

#include<stack>

#include<iomanip>

#include<cmath>

#include<queue>

#include<algorithm>

#include<stdio.h>

using namespace std;

# define ll long long

# define inf 0x3f3f3f3f

const int maxn = 800+100;

struct node

{

    int to;

    int nex;

    double cost;

} edge[maxn*maxn];

int n,m,l,r;

int head[maxn],num,vis[maxn],out[maxn];

double dis[maxn];

void init()

{

    num=0;

    for(int i=0; i<=n+m+100; i++)

    {

        head[i]=-1;

        dis[i]=inf*1.0;

        vis[i]=0;

        out[i]=0;

    }

}

void addedge(int fr,int to,double cost)

{

    edge[num].to=to;

    edge[num].cost=cost;

    edge[num].nex=head[fr];

    head[fr]=num++;

}

int spfa()

{

    vis[1]=1;

    dis[1]=0;

    queue<int>q;

    q.push(1);

    while(!q.empty())

    {

        int tmp=q.front();

        q.pop();

        if(++out[tmp]>(int)sqrt(n+m))

            return -1;

        vis[tmp]=0;

        for(int i=head[tmp]; i!=-1; i=edge[i].nex)

        {

            int u=edge[i].to;

            if(dis[u]>dis[tmp]+edge[i].cost)

            {

                dis[u]=dis[tmp]+edge[i].cost;

                if(vis[u])

                    continue;

                vis[u]=1;

                q.push(u);

            }

        }

    }

    return 1;

}

int main()

{

    while(~scanf("%d %d %d %d",&n,&m,&l,&r))

    {

        init();

        int tmp;

        for(int i=1; i<=n; i++)

        {

            for(int j=1; j<=m; j++)

            {

                scanf("%d",&tmp);

                double r1=log(r*1.0/(tmp*1.0));

                double l1=log(l*1.0/(tmp*1.0));

                addedge(i,j+n,r1);

                addedge(j+n,i,-l1);

            }

        }

        int ans=spfa();

        if(ans==-1)

            printf("NO\n");

        else

            printf("YES\n");

    }

    return 0;

}