HDU 3666 the matrix problemdifferential constraint + stack optimization SPFA negative ring

The question ： Give a N∗M Matrix C, It is required to construct two sequences a1,a2,…,an and b1,b2,…,bm, The order of the matrix i Multiply the row element by ai, The order of the matrix j Column element divided by bj, Each element of the final matrix Cij∈[L,U]. If it can be constructed successfully , The output YES, Otherwise output NO.

Answer key ： Difference constraint + Stack optimization spfa
The constraint equation can be obtained ：$L<=c\ast ai/bj<=U$

Habit is the longest way , So it can be converted into ：
$ai/bj>=L/c$ and $-ai/bj>=-U/c$

Take... On both sides log It can be converted to normal addition and subtraction .

Then the question goes directly bfs Negative ring, i.e >n+m Meeting t, See the root sign , But I don't know how to prove , You can actually use dfs Negative link , That is, keep running this ring , This will be very efficient , We use stack simulation dfs It's just the process of .

Be careful double.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, l, u, a;
struct node {
    
    int v, nxt;
    double w;
}edge[maxn << 2];
int vis[maxn], head[maxn], mark[maxn], k, s;
double d[maxn];
void add(int u, int v, double w) {
    
    edge[++k].nxt = head[u];
    edge[k].v = v;
    edge[k].w = w;
    head[u] = k;
}
//bool spfa() {
    
// for (int i = 1; i <= n + m; i++) {
    
// vis[i] = mark[i] = 0;
// d[i] = -0x3f3f3f3f; // Longest route version 
// }
// queue<int>q;
// q.push(s);
// mark[s] = vis[s] = 1;
// d[s] = 0;
// while (!q.empty()) {
    
// int u = q.front(); q.pop();
// vis[u] = 0;
// for (int i = head[u]; i; i = edge[i].nxt) {
    
// int v = edge[i].v;
// double w = edge[i].w;
// if (d[v] < d[u] + w) {
    
// d[v] = d[u] + w;
// if (vis[v]) continue;
// vis[v] = 1;
// if(++mark[v] > sqrt(n + m)) return false; // Negative loop  n+1 Only above can there be a negative ring 
// q.push(v);
// }
// }
// }
// return true;
//}
int q[maxn];
bool spfa() {
    
    for (int i = 1; i <= n + m; i++) {
    
        d[i] = -0x3f3f3f3f; 
        vis[i] = mark[i] = 0;
    }
    mark[s] = vis[s] = 1;
    d[s] = 0;
    int ed = 0;
    //q[++ed] = s;
    stack<int> q;
    q.push(s);
    while (q.size()) {
    
        //int u = q[ed--];
        int u = q.top();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].nxt) {
    
            int v = edge[i].v;
            double w = edge[i].w;
            if (d[v] < d[u] + w) {
    
                d[v] = d[u] + w;
                if (vis[v]) continue;
                vis[v] = 1;
                if (++mark[v] > n + m) return false;
                //q[++ed] = v;
                q.push(v);
            }
        }
    }
    return true;
}
int main() {
    
	while (~scanf("%d%d%d%d", &n, &m, &l, &u)) {
    
        k = 0;
        memset(head, 0, sizeof(head));
		for (int i = 1; i <= n; i++) {
    
			for (int j = 1; j <= m; j++) {
    
				scanf("%d", &a);
                add(n + j, i, log(1.0 * l / a));
                add(i, j + n, -log(1.0 * u / a));
			}
		}
        s = 1;
        if (spfa()) puts("YES");
        else puts("NO");
	}
	return 0;
}