Hdu 3666(差分约束)

hdu 3666

由题意可知, $$L <= C(i,j) * a_i/b_j <= U$$
可以都除以$C(i,j)$, 得 $$L/C(i,j) <= a_i/b_j <= U/C(i,j)$$
此时都是除法,不满足差分约束

看两个性质
$log(a/b) = log(a) - log(b)$
$log(a*b) = log(a) + log(b)$

那么原式可以变为
$$log(L/C(i,j)) <= log(a_i/b_j) <= log(U/C(i,j))$$
$$log(L) - log(C(i,j)) <= log(a_i) - log(b_j) <= log(U) - log(C(i,j))$$
将$a_i, b_j$看做是一个元素,就可以建立差分约束系统求解是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "hdu3666"
using namespace std;
const int MAXN = 400 * 400 + 5;
struct edge
{
int v;
double w;
}ed[MAXN*2];
int en;
vector<int> G[MAXN];
struct sdc
{
double dis[MAXN];
int cir[MAXN], vi[MAXN];
int n;
void init(int n)
{
en = 0;
this->n = n;
for (int i=1;i<=n;i++) G[i].clear();
}
void addedge(int x, int y, double c) // a - b <= c
{
en++, ed[en].v = x, ed[en].w = c, G[y].push_back(en);
}
int solve()
{
queue<int> q;
for (int i=1;i<=n;i++) dis[i] = 0, cir[i] = 1, vi[i] = true, q.push(i);
while (!q.empty())
{
int p = q.front(); q.pop(); vi[p] = false;
for (int i=0;i<G[p].size();i++)
{
int v = ed[G[p][i]].v;
double w = ed[G[p][i]].w;
if (dis[v]>dis[p]+w)
{
dis[v] = dis[p] + w;
if (!vi[v])
{
vi[v] = true;
cir[v]++; if (cir[v]>4) return false;//坑,>4只是卡的,>n会无限TLE TAT
q.push(v);
}
}
}
}
return true;
}
}sd;
int n, m;
double L, U, l_L, l_U;
void init()
{
sd.init(n*n);
l_L = log(L), l_U = log(U);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
double c, l_c; scanf("%lf", &c), l_c = log(c);
// a 1~n, b n+1~2n
sd.addedge(i, j+n, l_U-l_c);
sd.addedge(j+n, i, l_c-l_L);
}
}
}
void solve()
{
if (sd.solve()) printf("YES\n"); else printf("NO\n");
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);
freopen(FN2".out","w",stdout);
#endif
while (scanf("%d%d%lf%lf", &n, &m, &L, &U)==4)
{
init();
solve();
}
return 0;
}
------ 本文结束 ------