UVALive 5094 THE MATRIX PROBLEM(差分约束)

题目大意

给定一个 $N \times M$ 的矩阵 $E_{i,j}$。问是否存在一组解 $N$ 个数 $a_1, a_2, …, a_N$ 与 $M$ 个数 $b_1, b_2, …, b_M$ 满足对矩阵的每个元素使 $E_{i,j}$ = $E_{i,j} \times a_i \div b_j$ 后,值大小的范围为 $[L,U]$。输出 $YES$ 或 $NO$。
$(1 \le N, M \le 400, 1 \le L \le U \le 10000)$

解题思路

差分约束

观察 $L / E_{i,j} \le a_i \div b_j \le U / E_{i,j}$,对于不等式组判断容易想到差分约束系统。

然而差分约束系统主要是针对“两个未知数的差小于等于(或大于等于)某个常数”的。因此可以考虑对不等式取 $log$,把除法转为减法,即 $log(L / E_{i,j}) \le log(a) - log(b) \le log(U / E_{i,j})$,接着跑 $spfa$ 就可以啦。

另外,本题 $spfa$ 需要使用双端队列优化下($SLF$: Small Label First)。代码中注释部分使用的是“栈优化”,感觉这种优化方式还是有点奇怪的,本题能过(不TLE)可能是因为数据的关系,总之不推荐…

解题代码

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
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 4e2 + 10;
const int MAXM = 4e5 + 10;
const int INF = 0x7fffffff;

struct Edge {
int to;
double cost;
int next;
Edge( int to = 0, double cost = 0, int next = 0 ) : to(to), cost(cost), next(next) {}
} G[MAXM];
int n, m, E[MAXN][MAXN];
int tot, head[MAXN << 1];
double d[MAXN << 1];
int cnt[MAXN << 1], st[MAXM];
bool inque[MAXN << 1];

void init()
{

tot = 0;
memset(head, -1, sizeof(head));
memset(inque, 0, sizeof(inque));
memset(cnt, 0, sizeof(cnt));
}
void addEdge(int u, int v, double cost)
{

G[tot] = Edge(v, cost, head[u]);
head[u] = tot++;
}
// bool spfa(int s)
// {
// int top = 0;
// fill(d, d + n + m + 1, INF);
// d[s] = 0;
// st[top++] = s;
// inque[s] = true;
// cnt[s] = 1;
// while( top ) {
// int u = st[--top];
// inque[u] = false;
// for( int i = head[u]; ~i; i = G[i].next ) {
// Edge &e = G[i];
// if( d[e.to] > d[u] + e.cost ) {
// if( ++cnt[e.to] > n + m + 1 ) {
// return false;
// }
// d[e.to] = d[u] + e.cost;
// if( !inque[e.to] ) {
// st[top++] = e.to;
// inque[e.to] = true;
// }
// }
// }
// }
// return true;
// }
bool spfa(int s)
{

fill(d, d + n + m + 1, INF);
d[s] = 0;
deque<int> dque;
dque.push_back(s);
inque[s] = true;
cnt[s] = 1;
while( !dque.empty() ) {
int u = dque.front(); dque.pop_front();
inque[u] = false;
for( int i = head[u]; ~i; i = G[i].next ) {
Edge &e = G[i];
if( d[e.to] > d[u] + e.cost ) {
if( ++cnt[e.to] > n + m + 1 ) return false;
d[e.to] = d[u] + e.cost;
if( !inque[e.to] ) {
if( dque.empty() || d[e.to] > d[dque.front()] ) dque.push_back(e.to);
else dque.push_front(e.to);
inque[e.to] = true;
}
}
}
}
return true;
}
int main()
{

int L, U;
while( ~scanf("%d %d %d %d", &n, &m, &L, &U) ) {
init();
for( int i = 1; i <= n; ++ i ) {
for( int j = 1; j <= m; ++ j ) {
scanf("%d", &E[i][j]);
addEdge(j + n, i, log(U * 1.0 / E[i][j]));
addEdge(i, j + n, log(E[i][j] * 1.0 / L));
}
}
int s = 0;
for( int i = 1; i <= n; ++ i ) addEdge(s, i, 0);
for( int j = 1; j <= m; ++ j ) addEdge(s, j + n, 0);
if ( spfa(s) ) puts("YES");
else puts("NO");
}

return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!