HDU 3666 THE MATRIX PROBLEM 差分约束

http://acm.hdu.edu.cn/showproblem.php pid=3666

题目大意：

给你个N*M的矩阵，问是否存在一个序列a[1……N]和b[1……m]，使得矩阵中的每个元素L<=C[i][j] * a[i] /b[j]<=U

思路：

对于这种不等式有没有解的，可以想到差分约束。。。。。

L<=C[i][j] * a[i] /b[j]<=U 变形为

L/C[i][j] <=a[i] /b[j]<=U /C[i][j]

两边取对数得：

log(L/C[I][J] )<=log(a[i])-log(b[j])<=log(UC[I][J] )

然后就是建图啦~

敲完代码后TLE。。。百度之，看是否负环判断人家是开了个根号。。。。

改了。。

无数次WA。。。。

检查老半天发现是dis数组我写int.....给我个豆腐好吗。。

改成double就AC了(queue(sqrt(n+m) 800MS)

后想起以前卡队列直接用栈过。。然后改了下（仍然是超过n+m）。1900+MS险过。。。。

而stack（sqrt(n+m))500MS。。。。。

#include 
  
   
#include
   
     #include
    
      #include
     
       #include 
      
        using namespace std; const int MAXN=(400<<1)+10; const int MAXM=MAXN*MAXN+10; int n,m; int head[MAXN],len; struct edge { int to,next; double val; }e[MAXM]; void add(int from,int to,double val) { e[len].to=to; e[len].val=val; e[len].next=head[from]; head[from]=len++; } bool spfa() { bool vis[MAXN]; int cnt[MAXN]; double dis[MAXN]; stack
       
         q; int tot=n+m; int num=sqrt(double(n+m+1)); for(int i=0;i
        
         num) return false; q.push(id); vis[id]=true; } } } } return true; } int main () { double L,U; while(~scanf("%d%d%lf%lf",&n,&m,&L,&U)) { memset(head,-1,sizeof(head)); len=0; for(int i=0;i