2010年10月9日
* File: Timus 1069. The Prufer code
* Author: xiaotian @ hnu
* Created on 2010年10月9日, 上午9:35
* 题解：思维题目。给定一棵树的编码方式，让还原这棵树。
* 编码方式：每次取编号最小的叶节点和与其相连的边删掉，写下这个叶节点的父亲节点。重复以上操作，直到只有一个节点的时候，这个节点编号必然是 n 。
* 还原方式：可以发现，不在后面出现的节点必然是目前这棵树的叶节点，所以用优先队列维护一个后面不再出现的节点的集合，然后用队首元素与当前节点连边即可
。
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<queue>
5 using namespace std;
6 #define N 8000
7 #define inf 0x7ffffff
8 vector<int>g[N];
9 int n, id[N],last[N];
10
11 struct node {
12 int k;
13 node(int a = 0) : k(a) {}
14 bool operator<(const node & r) const { return r.k<k; }
15 };
16 priority_queue<node>q;
17
18 int main() {
19 int k;
20 n = 0;
21 memset(last, -1, sizeof (last));
22 while (scanf("%d", &k) != EOF) { id[n] = k; last[k] = n++; }
23 n++; while (!q.empty()) q.pop();
24 for (int i = 1; i <= n; i++) {
25 if (last[i] == -1) q.push(node(i));
26 g[i].clear();
27 }
28 for (int i = 0; i < n - 1; i++) {
29 k = q.top().k; q.pop();
30 g[k].push_back(id[i]);
31 g[id[i]].push_back(k);
32 if (i == last[id[i]]) q.push(node(id[i]));
33 }
34 for (int i = 1; i <= n; i++) {
35 printf("%d:", i);
36 sort(g[i].begin(), g[i].end());
37 for (int j = 0; j < g[i].size(); j++)
38 printf(" %d", g[i][j]);
39 puts("");
40 }
41 return 0;
42 }
2010年10月8日
优先队列bfs求最短路
1 /*
2 * File: PKU 3635 Full Tank?
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月8日, 下午4:27
5 * 题解：优先队列bfs
6 */
7 #include<iostream>
8 #include<math.h>
9 #include<queue>
10 #include<stdio.h>
11 #include<algorithm>
12 #include<string.h>
13 #include<vector>
14 using namespace std;
15 #define N 1008
16 #define inf 0x7fffffff
17
18 struct node {
19 int v, dist;
20
21 node(int a = 0, int b = 0) : v(a), dist(b) {
22 }
23 };
24
25 struct Node {
26 int v,rest,cost;
27
28 Node(int a = 0, int b = 0, int c = 0) : v(a), rest(b), cost(c) {
29 }
30 bool operator<(const Node &r) const{
31 return r.cost < cost;
32 }
33 };
34 vector<node>g[N];
35 int dp[N][102];
36 bool vist[N][102];
37 int n, m, a[N], V, S, T, ans;
38 priority_queue<Node>q;
39
40 int bfs() {
41 int x, y, z;
42 while (!q.empty())
43 q.pop();
44 q.push(Node(S, 0, 0));
45 dp[S][0] = 0;
46 while (!q.empty()) {
47 Node p = q.top();
48 q.pop();
49 x = p.v, y = p.rest, z = p.cost;
50 vist[x][y] = 1;
51 if (x == T) return z;
52 if (y + 1 <= V && !vist[x][y + 1] && dp[x][y + 1] > dp[x][y] + a[x]) {
53 dp[x][y + 1] = dp[x][y] + a[x];
54 q.push(Node(x, y + 1, dp[x][y + 1]));
55 }
56 for (int i = 0; i < g[x].size(); i++) {
57 int t = g[x][i].v;
58 int k = y - g[x][i].dist;
59 if (k >= 0 && !vist[t][k] && z < dp[t][k]) {
60 dp[t][k] = z;
61 q.push(Node(t, k, dp[t][k]));
62 }
63 }
64 }
65 return -1;
66 }
67
68 int main() {
69 int i, j;
70 while (scanf("%d%d", &n, &m) != EOF) {
71 for (i = 0; i < n; i++) {
72 scanf("%d", &a[i]);
73 g[i].clear();
74 }
75 int u, v, w;
76 for (i = 0; i < m; i++) {
77 scanf("%d%d%d", &u, &v, &w);
78 g[u].push_back(node(v, w));
79 g[v].push_back(node(u, w));
80 }
81 int tc;
82 scanf("%d", &tc);
83 while (tc--) {
84 scanf("%d%d%d", &V, &S, &T);
85 memset(vist, 0, sizeof (vist));
86 for (i = 0; i < n; i++)
87 for (j = 0; j <= 100; j++)
88 dp[i][j] = inf;
89 ans = bfs();
90 if (ans == -1)
91 printf("impossible\n");
92 else
93 printf("%d\n", ans);
94 }
95 }
96 return 0;
97 }
PKU 3463 Sightseeing
题解：求最短路以及次短路（比最短路长1）的路的条数，递推求解，四种转移
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#include<set>
#include<math.h>
using namespace std;
#define N 1008
#define inf 0x7ffffff
struct edge {
int e, d;
edge(int a, int b) : e(a), d(b) {}
};
struct node {
int e, d, f;
node(int a, int b, int c) : e(a), d(b), f(c) {}
bool operator<(const node & a)const {
return d > a.d;
}
};
vector <edge> g[N];
int dis[N][2];
int cnt[N][2];
int n,m,s,t;
void dijkstra() {
int i, j;
priority_queue <node> q;
memset(cnt, 0, sizeof (cnt));
for (i = 0; i <= n; i++) dis[i][1] = dis[i][0] = inf;
dis[s][1] = dis[s][0] = 0;
cnt[s][0] = 1;
q.push(node(s, 0, 0));
while (!q.empty()) {
node p = q.top();
q.pop();
int k = p.e,d = p.d,f = p.f;
if (dis[k][f] != d) continue;
for (j = 0; j < g[k].size(); j++) {
int e = g[k][j].e;
int dist = g[k][j].d+d;
if ((dis[e][0] > dist)) { /*新值小于最短路*/
if (dis[e][0] != inf) {
dis[e][1] = dis[e][0];
q.push(node(e, dis[e][1], 1));
}
dis[e][0] = dist;
cnt[e][1] = cnt[e][0];
cnt[e][0] = cnt[k][f];
q.push(node(e, dist, 0));
continue;
}
if (dis[e][0] == dist) { /*新值等于最短路*/
cnt[e][0] += cnt[k][f];
continue;
}
if ((dis[e][1] > dist)) { /*新值大于最短路，小于次短路*/
dis[e][1] = dist;
cnt[e][1] = cnt[k][f];
q.push(node(e, dist, 1));
continue;
}
if (dis[e][1] == dist){ /*新值等于次短路*/
cnt[e][1] += cnt[k][f];
continue;
}
}
}
}
int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
g[i].clear();
for (int i = 0; i < m; i++) {
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
g[a].push_back(edge(b, c));
}
scanf("%d%d", &s, &t);
dijkstra();
int ans = cnt[t][0];
if (dis[t][0] + 1 == dis[t][1])
ans += cnt[t][1];
printf("%d\n", ans);
}
return 0;
}
2010年10月6日
最小斯泰纳树，直接用吉大模板
1 /*
2 * File: HNU 10862 Ticket to Ride
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月6日, 下午7:48
5 * 题解：最小斯泰纳树，直接套板
6 */
7
8 #include<stdio.h>
9 #include<iostream>
10 #include<string>
11 #include<queue>
12 #include<map>
13 #include<set>
14 #include<math.h>
15 using namespace std;
16 #define N 1000
17 #define A 8
18 #define inf 0x7ffffff
19 int vis[N], id[A]; //id[]: A中点的标号
20 int d[N][N], dp[1 << A][N]; //dp[i][v]: 点v到点集i的最短距离
21 map<string, int>mp, fg;
22
23 int min(int a, int b) {
24 return a < b ? a : b;
25 }
26
27 void steiner(int n, int a) {
28 int i, j, k, mx, mk, top = (1 << a);
29 for (k = 0; k < n; k++)
30 for (i = 0; i < n; i++)
31 for (j = 0; j < n; j++)
32 if (d[i][j] > d[i][k] + d[k][j])
33 d[i][j] = d[i][k] + d[k][j];
34 for (i = 0; i < a; i++) { // vertex: 0 ~ n-1
35 for (j = 0; j < n; j++)
36 dp[1 << i][j] = d[j][ id[i] ];
37 }
38 for (i = 1; i < top; i++) {
39 if (0 == (i & (i - 1))) continue;
40 memset(vis, 0, sizeof (vis));
41 for (k = 0; k < n; k++) { // init
42 for (dp[i][k] = inf, j = 1; j < i; j++)
43 if ((i | j) == i &&
44 dp[i][k] > dp[j][k] + dp[i - j][k])
45 dp[i][k] = dp[j][k] + dp[i - j][k];
46 }
47 for (j = 0; mx = inf, j < n; j++) { // update
48 for (k = 0; k < n; k++)
49 if (dp[i][k] <= mx && 0 == vis[k])
50 mx = dp[i][mk = k];
51 for (k = 0, vis[mk] = 1; k < n; k++)
52 if (dp[i][mk] > dp[i][k] + d[k][mk])
53 dp[i][mk] = dp[i][k] + d[k][mk];
54 }
55 }
56 }
57
58 int main() {
59 int n, m, a = 8, w;
60 char s1[25], s2[25];
61 while (scanf("%d%d\n", &n, &m) != EOF) {
62 if (n == 0 && m == 0) return 0;
63 mp.clear();
64 for (int i = 0; i < n; i++) {
65 scanf("%s",s1);
66 mp[s1] = i + 1;
67 }
68 for (int i = 0; i <= n; i++)
69 for (int j = 0; j <= n; j++) d[i][j] = i==j?0:inf;
70 for (int i = 0; i < m; i++) {
71 scanf("%s %s %d", s1, s2, &w);
72 int u = mp[s1] - 1;
73 int v = mp[s2] - 1;
74 d[u][v] = d[v][u] = min(d[u][v], w);
75 }
76 fg.clear();
77 for (int i = 0; i < 8; i++) {
78 scanf("%s", s1);
79 id[i] = mp[s1] - 1;
80 }
81 steiner(n, a);
82 int i, j, z, x, y, k, b;
83 for (i = 0, b = inf; z = 0, i < 256; b > z ? b = z : b, i++)
84 for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)
85 for (k = 0; k < 8; k += 2)
86 if ((i >> k & 3) == j)
87 y += 3 << k, x = id[k];
88 printf("%d\n",b);
89 }
90 }
题意是给一个无向图，求添加最少的边使得图中没有桥。
（这样理解：例如一个公路网，有时候某些公路损坏需要检修的时候，为了不影响正常的交通，这个公路网中应该存在另外的路径使得要检修的路所连接的两个点依然联通。如果不存在这样的路径，那么所检修的这条路就叫做无向图中的桥。这个命名很生动。）
求解：先求出双连通分量，将其缩点。最后会得到一棵树。找出度为1的点，设为 T ，那么至少要添加的边数位：(T+1)/2。
怎么证明这个结论？不太懂。这么想吧：首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一
起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是 (T+1)/2 次，把所有点收缩到了一
起。
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<queue>
5 #include<map>
6 #include<set>
7 #include<math.h>
8 using namespace std;
9 #define N 5008
10 #define inf 0x7ffffff
11 vector<int> g[N];
12 int cnt, low[N], pre[N], vis[N], deg[N];
13 void dfs(int u, int v) {
14 vis[u] = 1;
15 pre[u] = cnt++, low[u] = pre[u];
16 for (int i = 0; i < g[u].size(); ++i) {
17 if (g[u][i] == v) continue;
18 if (!vis[g[u][i]]) dfs(g[u][i], u);
19 if (low[g[u][i]] < low[u]) low[u] = low[g[u][i]];
20 }
21 vis[u] = 2;
22 }
23 int ok(int x, int y) {
24 for (int i = 0; i < g[x].size(); ++i)
25 if (y == g[x][i]) return 0;
26 return 1;
27 }
28 int main() {
29 int i, j, u, v, n, m, ans;
30 while (scanf("%d %d", &n, &m) != EOF) {
31 for (i = 0; i <= n; ++i) g[i].clear();
32 while (m--) {
33 scanf("%d %d", &u, &v);
34 if (ok(u, v)) {
35 g[u].push_back(v);
36 g[v].push_back(u);
37 }
38 }
39 memset(vis, 0, sizeof (vis));
40 cnt = 0;
41 dfs(1, 1);
42 memset(deg, 0, sizeof (deg));
43 for (i = 1; i <= n; ++i) {
44 for (j = 0; j < g[i].size(); ++j)
45 if (low[i] != low[g[i][j]])
46 deg[low[i]]++;
47 }
48 for (ans = i = 0; i <= n; ++i)
49 if (deg[i] == 1) ++ans;
50 printf("%d\n", (ans + 1) / 2);
51 }
52 return 0;
53 }
2010年10月5日
/* 1056. Computer net
* File: Timus
* Author: xiaotian @ hnu
* Created on 2010年10月5日, 下午3:06
* 题解：twice bfs 第一次找离节点1最远的点K，再找离K最远的点X，
* K--X就是最长链，链上的中点就是中心 O(n)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 10010;
struct node {
int en;
node * next;
node() {
next = NULL;
}
};
node nhead[N];
struct QUEUE {
int val;
int level;
};
QUEUE que[N];
int head, tail;
int line[N];
int flag[N];
int fat[N];
int n;
inline int min(int a,int b) { return a<b?a:b; }
inline int max(int a,int b) { return a>b?a:b; }
void input() {
memset(fat, -1, sizeof (fat));
int en;
for (int i = 2; i <= n; i++) {
scanf("%d", &en);
fat[i] = en;
node *temp1 = (node *) malloc(sizeof (node));
temp1->en = en;
temp1->next = nhead[i].next;
nhead[i].next = temp1;
node *temp2 = (node *) malloc(sizeof (node));
temp2->en = i;
temp2->next = nhead[en].next;
nhead[en].next = temp2;
}
}
void bfs(int sn) {
memset(flag, 0, sizeof (flag));
que[tail].val = sn;
que[tail++].level = 1;
flag[sn] = 1;
int curn;
node *p;
while (head < tail) {
curn = que[head].val;
p = nhead[curn].next;
while (NULL != p) {
if (0 == flag[p->en]) {
flag[p->en] = 1;
que[tail].val = p->en;
que[tail++].level = que[head].level + 1;
}
p = p->next;
}
head++;
}
}
void process() {
head = tail = 0;
bfs(1);
int leaf = que[tail - 1].val;
head = tail = 0;
bfs(leaf);
}
void output() {
line[0] = 0;
int p = tail - 1;
int maxlen = que[tail - 1].level;
line[maxlen] = que[tail - 1].val;
for (int i = maxlen - 1; i >= 1; i--) {
while (que[p].level > i && p >= 0) p--;
while (fat[que[p].val] != line[i + 1] && fat[line[i + 1]] != que[p].val && p >= 0) p--;
line[i] = que[p].val;
}
int x = (maxlen + 1) / 2;
if (1 == (maxlen & 1))
printf("%d\n", line[x]);
else
printf("%d %d\n", min(line[x], line[x + 1]), max(line[x], line[x + 1]));
}
int main() {
while (scanf("%d", &n) != EOF) {
input();
process();
output();
}
return 0;
}
2010年10月4日
1 /*
2 * File: Timus 1450. Russian pipelines
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月4日, 下午4:06
5 * 题解：DP求最长路
6 */
7 #include<stdio.h>
8 #include<iostream>
9 #include<string.h>
10 using namespace std;
11 #define N 505
12 #define INF 0x7ffffffffLL
13 long long G[N][N], dp[N];
14 bool v[N];
15 int s, t, m, n;
16
17 void dfs(int x) {
18 v[x] = 1;
19 for (int i = 0; i <= n; i++)
20 if (G[i][x] && !v[i]) dfs(i);
21 }
22
23 long long solve(int x) {
24 if (dp[x] != -INF) return dp[x];
25 long long best = -INF, tmp;
26 for (int i = 1; i <= n; i++) {
27 if (G[x][i] && v[i]) {
28 tmp = solve(i) + G[x][i];
29 best = best > tmp ? best : tmp;
30 }
31 }
32 if (best < 0) best = -INF;
33 return dp[x] = best;
34 }
35
36 int main() {
37 while (scanf("%d%d", &n, &m) != EOF) {
38 memset(G, 0, sizeof (G));
39 memset(v, 0, sizeof (v));
40 for (int i = 0; i <= n; i++)
41 dp[i] = -INF;
42 while (m--) {
43 int a, b, c;
44 scanf("%d%d%d", &a, &b, &c);
45 G[b][a] = c > G[b][a] ? c : G[b][a];
46 }
47 scanf("%d%d", &s, &t);
48 dfs(s);
49 dp[s] = 0;
50 long long ret = solve(t);
51 if (ret < 0) printf("No solution");
52 else printf("%lld\n", ret);
53 }
54 return 0;
55 }
56
Timus 1742. Team building
1 /*
2 * File: Timus 1742. Team building
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月4日, 下午2:54
5 * 题解：
6 */
7 #include <iostream>
8 #include <string>
9 #include <set>
10 #include <map>
11 #include <vector>
12 #include <algorithm>
13 using namespace std;
14 const int N = 100008;
15
16 int deg[N];
17 int nxt[N];
18 int vised[N], cnt, beg;
19
20 int dfs(int a) {
21 if (vised[a])
22 if (vised[a] >= beg) return vised[a] + 1 - beg;
23 else return cnt - beg;
24 vised[a] = cnt++;
25 return dfs(nxt[a]);
26 }
27
28 int main() {
29 int n;
30 while (scanf("%d", &n) != EOF) {
31 cnt = 1;
32 memset(deg, 0, sizeof (deg));
33 for (int i = 0; i < n; i++) {
34 scanf("%d", nxt + i);
35 nxt[i]--;
36 deg[nxt[i]]++;
37 }
38 int maxR = 0, minR = 0;
39 for (int i = 0; i < n; i++, cnt++)
40 if (!deg[i]) {
41 beg = cnt;
42 minR++;
43 maxR += dfs(i);
44 }
45 for (int i = 0; i < n; i++)
46 if (!vised[i]) {
47 minR++, maxR++;
48 int p = i;
49 while (!vised[p]) {
50 vised[p] = 1;
51 p = nxt[p];
52 }
53 }
54 printf("%d %d\n",minR,maxR);
55 break;
56 }
57 return 0;
58 }
2010年10月2日
/*
* File: Timus 1040. Airline company
* Author: xiaotian @ hnu
* Created on 2010年10月2日, 上午9:34
* 题解：一次找极长路（即两边不能再加边），将他们依次编号，然后删掉这些边。直至图中没有边为止。输出解即可。
* 不会出现没有解的情况。
*/
1 #include <iostream>
2 #include<string.h>
3 #include<iostream>
4 #define N 55
5 using namespace std;
6 int n, m;
7 int g[N][N];
8 int link[N][N];
9 int num[N*N];
10 int now;
11 bool vis[N];
12 bool p[N*N];
13
14 void dfs(int x) {
15 for (int i = 1; i <= g[x][0]; ++i)
16 if (!p[link[x][i]]) {
17 p[link[x][i]] = true;
18 num[link[x][i]] = ++now;
19 if (!vis[g[x][i]]) {
20 vis[g[x][i]] = true;
21 dfs(g[x][i]);
22 }
23 }
24 }
25
26 int main() {
27 while (scanf("%d %d", &n, &m) != EOF) {
28 memset(vis,0,sizeof(vis));
29 memset(p,0,sizeof(p));
30 now=0;
31 for (int i = 0; i <= n; i++) g[i][0] = link[i][0] = 0;
32 for (int i = 1; i <= m; ++i) {
33 int a, b;
34 scanf("%d %d", &a, &b);
35 g[a][++g[a][0]] = b;
36 g[b][++g[b][0]] = a;
37 link[a][++link[a][0]] = i;
38 link[b][++link[b][0]] = i;
39 }
40 vis[1] = true;
41 dfs(1);
42 puts("YES");
43 for (int i = 1; i <= m; ++i) printf("%d ", num[i]);
44 }
45 }
2010年10月1日
/*
* 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 }