题目传送门


题意：给你一个n*m的矩阵，和一个区间上下界L，U，问你是否能找出n个数a1,a2,a3,......,an和m个数b1,b2,b3,......,bm，使得矩阵中的第i行的数乘以ai得到的值范围在[L,U]内，而且矩阵中第j列的数除以bj得到的值范围也在[L,U]内，能找到你就输出YES，否则NO。

输入第一行为n,m,L,U

接下来一个n*m的矩阵Aij

分析：做差分约束的题首先我们得找到一种关系（两个不定数相减大于等于或者小于等于某个值）。根据题意我们可以简单得到下面的关系：

（1） L<=Aij * ai <=U （第一个要求）

（2） L<=Aij / bj <=U （第二个要求）

看到上面两个式子，似乎和差分约束的不等式关系不符，但是我们可以通过取对数使其变成两数相加或者两数相减，通过取对数可以得到下面变形式：

（1） log(L) <= log(Aij) +log(ai) <=log(U)

（2） log(L) <= log(Aij) - log(bj) <=log(U)

哈哈哈，两式相加可以得到： 2*log(L) <= 2*log(Aij) +log(ai) -log(bj) <=2*log(U)

                            移项可得： 2*log(L)-2*log(Aij) <=log(ai) - log(bj) <= 2*log(U)-2*log(Aij)

那么就可以在i到j+n之间建边了，边长就是上式中的值，具体看下代码就是了，但是此题卡队列，用一般的方法入队次数大于点数判环会TLE，在这里可以用以下两种方法优化：

1. 如果点数为n，那么其中一个点的入队次数大于sqrt(n) 就有环；

2.所有点的入队次数大于k*n，那么有环，k一般为2.....


ac代码如下：


#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 50010
#define inf 0x3fffffff

struct node{
  int en,next;
  double len;
}E[maxn*10];
int head[maxn],top;
int n,m;
void Add_Edge(int st,int en,double len)
{
    E[top].en=en;
    E[top].len=len;
    E[top].next=head[st];
    head[st]=top;
    top++;
}

double dis[maxn];
bool vis[maxn];
int cnt[maxn];

bool spfa()
{
    for(int i=0;i<=n+m;i++)
    {
        vis[i]=false;
        cnt[i]=0;
        dis[i]=inf;
    }
    queue<int>q;
    dis[1]=0.0;
    cnt[1]++;
    vis[1]=true;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=false;
        for(int j=head[x];j!=-1;j=E[j].next)
        {
            if(dis[E[j].en]>dis[x]+E[j].len)
            {
                dis[E[j].en]=dis[x]+E[j].len;
                if(!vis[E[j].en])
                {
                    q.push(E[j].en);
                    cnt[E[j].en]++;
                    if(cnt[E[j].en]>(int)sqrt(n+m))
                        return false;
                    vis[E[j].en]=true;
                }
            }
        }
    }
    return true;
}

int main()
{
    double l,u,L,U;
    while(~scanf("%d%d%lf%lf",&n,&m,&L,&U))
    {
        top=0;
        memset(head,-1,sizeof(head));
        /// 2*log(L)-2*log(Aij) <=log(ai) - log(bj) <= 2*log(U)-2*log(Aij)
        l=2.0*log(L),u=2.0*log(U);
        double x;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%lf",&x);
                x=2*log(x);
                Add_Edge(j,i+m,u-x);
                Add_Edge(i+m,j,x-l);
            }
        }
        bool flag=spfa();
        if(flag)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}