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;inum)
                        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