HDU 3666 THE MATRIX PROBLEM 解題報告（差分限制）

THE MATRIX PROBLEM

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 7557    Accepted Submission(s): 1941

Problem Description You have been given a matrix C N*M, each element E of C N*M is positive and no more than 1000, The problem is that if there exist N numbers a1, a2, … an and M numbers b1, b2, …, bm, which satisfies that each elements in row-i multiplied with ai and each elements in column-j divided by bj, after this operation every element in this matrix is between L and U, L indicates the lowerbound and U indicates the upperbound of these elements.  

Input There are several test cases. You should process to the end of file.

Each case includes two parts, in part 1, there are four integers in one line, N,M,L,U, indicating the matrix has N rows and M columns, L is the lowerbound and U is the upperbound (1<=N、M<=400,1<=L<=U<=10000). In part 2, there are N lines, each line includes M integers, and they are the elements of the matrix.

Output If there is a solution print "YES", else print "NO".  

Sample Input

3 3 1 6
2 3 4
8 2 6
5 2 9
        

Sample Output

YES
 
        

Source 2010 Asia Regional Harbin  

    解題報告：第一眼看上去，沒想到是差分限制……亂搞搞然後肯定WA了。

    根據題意，我們要找出序列a和序列b，使得 L <= Cij * ai / bj <= R。兩邊取log，可得 log(L) <= log(Cij) + log(ai) - log(bj) <= R，然後以此建構差分限制，使用SPFA判環即可。

    關于圖的存儲方法，對于這樣一個特殊的圖，個人覺得使用鄰接矩陣更好。當然在周遊邊的時候加個判斷。代碼如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define ff(i, n) for(int i=0,END=(n);i<END;i++)
#define fff(i, n, m) for(int i=(n),END=(m);i<=END;i++)
#define dff(i, n, m) for(int i=(n),END=(m);i>=END;i--)
#define travel(i, u) for(int e=first[u], v=vv[first[u]]; ~e; e=nxt[e], v=vv[e])
#define mid ((l+r)/2)
#define bit(n) (1ll<<(n))
#define clr(a, b) memset(a, b, sizeof(a))

void work();

int main() {
    work();
    return 0;
}

/**************************Beautiful GEGE**********************************/

const int maxn = 400 + 400 + 5;
double edge[maxn][maxn];

int stack[maxn * maxn], cnt[maxn], top;
double d[maxn];
bool inStack[maxn];
bool hasLoop(int n, int m) {
    ff(i, n + m) stack[top ++] = i, inStack[i] = true, cnt[i] = 1, d[i] = 0;

    while (top) {
        int u = stack[-- top];
        inStack[u] = false;

        int start = 0, end = n;
        if (u < n) start = n, end = n + m;
        fff (v, start, end - 1) if (d[v] > d[u] + edge[u][v]) {
            d[v] = d[u] + edge[u][v];

            if (! inStack[v]) {
                stack[top ++] = v, inStack[v] = true, cnt[v] ++;

                if (cnt[v] >= n + m) return true;
            }
        }
    }

    return false;
}

void work() {
    int n, m, l, u;
    while(scanf("%d%d%d%d", &n, &m, &l, &u) == 4) {
        double lower = log(l);
        double upper = log(u);

        ff(i, n) ff(j, m) {
            int value;
            scanf("%d", &value);
            double log_value = log(value);

            int u = i, v = n + j;
            edge[u][v] = log_value - lower;
            edge[v][u] = upper - log_value;
        }

        puts(hasLoop(n, m) ? "NO" : "YES");
    }
}