/*
* File: HDU 3666 THE MATRIX PROBLEM
* Author: xiaotian @ hnu
* Created on 2010年9月30日, 下午12:28
* 题解：哈尔滨现场赛G题，看到题目想到是差分约束，但是一时没想出怎么建图
* 贺神说log下不就可以很容易的建图了，于是被点化。
* 建图还是比较裸的。直接spfa跑一下有负环就不可行，否则可行。
* 刚开始谢了一个版本TLE了，原因是 cnt[V[e]] > sqrt(1.0 * n) 就可以直接判断了，我却要等到它大于 n 。
* 写了两个版本的，第一个版本是链表实现的，发现速度很慢，1900+ms，时间上有点擦边。
* 又写了一个数组版本的，速度相对快一点,大约能降到 1000+ms 。
*/
版本一：
1 #include<stdio.h>
2 #include<string.h>
3 #include<queue>
4 #include<math.h>
5 #include<algorithm>
6 using namespace std;
7 #define N 408
8 #define inf 0x3fffffff
9 int n, m, ne;
10 double low, hig;
11 int vis[2 * N], num[2 * N];
12 double d[2 * N];
13
14 struct node {
15 int adj;
16 double w;
17 node *next;
18 } *head[2 * N], g[2 * N * N];
19
20 void addedge(int x, int y, double w) {
21 g[ne].adj = y;
22 g[ne].w = w;
23 g[ne].next = head[x];
24 head[x] = &g[ne];
25 ne++;
26 }
27
28 void build() {
29 memset(head, 0, sizeof (head));
30 ne = 0;
31 double a = log(hig);
32 double b = log(low);
33 for (int i = 0; i < n; i++)
34 for (int j = 0; j < m; j++) {
35 double c;
36 scanf("%lf", &c);
37 c = log(c);
38 addedge(i + 1, j + n + 1, a - c);
39 addedge(j + n + 1, i + 1, c - b);
40 }
41 }
42
43 int solve() {
44 int i;
45 queue<int> q;
46 for (i = 1; i <= n; i++) {
47 q.push(i);
48 d[i] = inf;
49 vis[i] = 1;
50 num[i] = 0;
51 }
52 while (!q.empty()) {
53 int x = q.front();
54 q.pop();
55 vis[x] = 0;
56 for (node *p = head[x]; p; p = p->next)
57 if (d[p->adj] > d[x] + p->w) {
58 d[p->adj] = d[x] + p->w;
59 if (!vis[p->adj]) {
60 vis[p->adj] = 1;
61 num[p->adj]++;
62 if (num[p->adj] >= (int) sqrt(1.0 * n)) return 0;
63 q.push(p->adj);
64 }
65 }
66 }
67 return 1;
68 }
69
70 int main() {
71 while (scanf("%d %d %lf %lf", &n, &m, &low, &hig) != EOF) {
72 build();
73 n += m;
74 int ans = solve();
75 puts(ans ? "YES" : "NO");
76 }
77 return 0;
78 }
版本二
：
1 #include<iostream>
2 #include<cmath>
3 #include<queue>
4 #define N 810
5 #define E 320010
6 using namespace std;
7
8 bool vis[N];
9 int cnt[N];
10 double dis[N];
11 int head[N];
12 int V[E], next[E];
13 double W[E];
14 int ne, n, m;
15
16 void addedge(int u, int v, double w) {
17 V[ne] = v;
18 W[ne] = w;
19 next[ne] = head[u];
20 head[u] = ne++;
21 }
22
23 void build(double l, double r) {
24 ne = 0;
25 l = log(l);
26 r = log(r);
27 memset(head, -1, sizeof (head));
28 for (int i = 0; i < n; i++)
29 for (int j = 0; j < m; j++) {
30 int a;
31 scanf("%d", &a);
32 double c = log(a);
33 addedge(j + n, i, r - c);
34 addedge(i, j + n, c - l);
35 }
36 n += m;
37 }
38
39 bool spfa() {
40 int i;
41 queue<int>q;
42 for (i = 0; i < n; i++) {
43 vis[i] = true;
44 dis[i] = 10000000;
45 q.push(i);
46 cnt[i] = 0;
47 }
48 dis[0] = 0;
49 while (!q.empty()) {
50 int u = q.front();
51 q.pop();
52 vis[u] = 0;
53 for (int e = head[u]; e != -1; e = next[e]) {
54 if (dis[u] + W[e] < dis[V[e]]) {
55 dis[V[e]] = dis[u] + W[e];
56 if (!vis[V[e]]) {
57 q.push(V[e]);
58 vis[V[e]] = 1;
59 if (++cnt[V[e]] > (int) sqrt(1.0 * n))
60 return 0;
61 }
62 }
63 }
64 }
65 return 1;
66 }
67
68 int main() {
69 double l, r;
70 while (scanf("%d%d%lf%lf", &n, &m, &l, &r) != EOF) {
71 build(l, r);
72 puts(spfa() ? "YES" : "NO");
73 }
74 return 0;
75 }