【題意】：給出一個N*M的矩陣C，C中每個元素都是正整數且不超過1000.問是否存在一個長度為N的序列a1，a2，……，aN和一個長度為M的序列b1，b2，……，bM使得矩陣C中的每一個元素Cij滿足 L <= Cij * ai / bj <= U。

【題解】：從題目中可以抽離出N * M個不等式，然后題目又要我們判斷可行解，這樣子很容易就想到差分約束系統。對于這個不等式，我們需要做點轉化，用一個log化簡一下即可。                         
                        L <= Cij * ai / bj <= U       =>       log L - log Cij <= log ai - log bj <= log U - log Cij.
              然后構圖找判負環即可，但是這個N*M高達800，所以queue的spfa會TLE，這里采用stack的spfa。

【代碼】：
 1 #include "iostream"
 2 #include "cstring"
 3 #include "cstdio"
 4 #include "cmath"
 5 using namespace std;
 6 #define maxn 1000
 7 #define maxm 1000000
 8 const double inf = 1 << 30;
 9 int n, m, s;
10 double l, u;
11 bool visit[maxn];
12 int eh[maxn], tot;
13 double dist[maxn];
14 struct Edge {
15     int u, v;
16     double cost;
17     int next;
18 }et[maxm];
19 
20 void init() {
21     tot = 0;
22     memset(eh, -1, sizeof(eh));
23 }
24 
25 void addedge(int u, int v, double cost) {
26     Edge e = {u, v, cost, eh[u]};
27     et[tot] = e;
28     eh[u] = tot++;
29 }
30 bool instack[maxn];
31 bool dfs_spfa(int u) {
32     if(instack[u]) return false;
33     instack[u] = true;
34     visit[u] = true;
35     for(int i = eh[u]; i != -1; i = et[i].next) {
36         int v = et[i].v;
37         double cost = et[i].cost;
38         if(dist[v] > dist[u] + cost) {
39             dist[v] = dist[u] + cost;
40             if(!dfs_spfa(v)) return false;
41         }
42     }
43     instack[u] = false;
44     return true;
45 }
46 
47 bool solve() {
48     memset(visit, false, sizeof(visit));
49     memset(instack, false, sizeof(instack));
50     memset(dist, 0, sizeof(dist));
51     for(int i = 1; i <= n + m; i++) {
52         if(!visit[i])
53             if(!dfs_spfa(i)) return false;
54     }
55     return true;
56 }
57 
58 int main() {
59     double tmp;
60     while(scanf("%d%d%lf%lf", &n, &m, &l, &u) != EOF) {
61         init();
62         for(int i = 1; i <= n; i++) {
63             for(int j = 1; j <= m; j++) {
64                 scanf("%lf", &tmp);
65                 addedge(j + n, i, log(u / tmp));
66                 addedge(i, j + n, -log(l / tmp));
67             }
68         }
69         if(solve()) printf("YES\n");
70         else printf("NO\n");
71     }
72     
73     return 0;
74 }