题目链接：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
");
else
printf("YES
");
}
return 0;
}