/* * 解法: 差分约束. * 根据题意能建立这样的不等式 Mij * Ai / Bj >= L, Mij * Ai / Bj <= U * 使用log将乘除法变为加减法 logMij + logAi - logBj >= logL, logMij + logAi - logBj <= logU * 由此建图, 再运行SPFA判断是否存在环. 判断环用DFS版的SPFA, 否则会超时 * DFS版SPFA详见IOI国家集训队论文 */ #include <iostream> #include <cmath> using namespace std; const int maxn = 405; const int maxv = 805; const int maxe = 320005; struct Graph { int idx; int head[maxv], pnt[maxe], nxt[maxe]; double val[maxe]; void addedge(int x, int y, double v) { pnt[idx] = y; val[idx] = v; nxt[idx] = head[x]; head[x] = idx++; } void init(int n) { memset(head, -1, n * 4); idx = 0; } } graph; double L, U, M[maxn][maxn], val[maxn]; int n, m, cnt[maxv]; bool vis[maxv]; bool ins[maxv]; void BuildGraph() { graph.init(n + m); int i, j; for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { graph.addedge(i, j + n, M[i][j] - U); graph.addedge(j + n, i, L - M[i][j]); } } } bool SPFA(int x) { if (ins[x]) return false; ins[x] = vis[x] = true; for (int p = graph.head[x]; p != -1; p = graph.nxt[p]) { int y = graph.pnt[p]; if (val[y] > val[x] - graph.val[p]) { val[y] = val[x] - graph.val[p]; if (!SPFA(y)) return false; } } ins[x] = false; return true; } bool Solve() { memset(vis, 0, n + m); memset(ins, 0, n + m); memset(val, 0, (n + m) * 8); for (int i = 0; i < n + m; i++) { if (!vis[i]) if (!SPFA(i)) return false; } return true; } int main() { int i, j; while (scanf("%d %d %lf %lf", &n, &m, &L, &U) != EOF) { L = log(L); U = log(U); for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { scanf("%lf", &M[i][j]); M[i][j] = log(M[i][j]); } } BuildGraph(); if (Solve()) printf("YES/n"); else printf("NO/n"); } return 0; }