HDU3666 THE MATRIX PROBLEM

Star 2022-07-11 20:19:35

#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>

using namespace std;

const int M = 360010;

int ver[M], ne[M], head[M];
double w[M]; 
int tot;

bool vis[M];

int n, m, l, r;

void add(int x, int y, double z) {
    ver[++tot] = y;
    w[tot] = z;
    ne[tot] =  head[x];
    head[x] = tot;
}

void init() {
    memset(ver, 0, sizeof(ver));
    memset(ne, 0, sizeof(ne));
    memset(head, 0, sizeof(head));
    memset(w, 0, sizeof(w));
    memset(vis, 0, sizeof(vis));
    tot = 0;
}

bool spfa() {
    stack<int> q;
    double dis[M];
    bool inque[M];
    int cnt[M];
    memset(dis, 0x7f, sizeof(dis));
    memset(inque, 0, sizeof(inque));
    memset(cnt, 0, sizeof(cnt));
    cnt[0] = 1;
    dis[0] = 0;
    inque[0] = true;
    q.push(0);
    while (!q.empty()) {
        int x = q.top();
        q.pop();
        vis[x] = true;
        inque[x] = false;
        for (int i = head[x]; i; i = ne[i]) {
            int &y = ver[i];
            if (dis[y] > dis[x] + w[i]) {
                cnt[y] += cnt[x];
                if (cnt[y] > n + m - 1) {
                    return true;
                }
                dis[y] = dis[x] + w[i];
                if (!inque[y]) {
                    inque[y] = true;
                    q.push(y);
                }
            }
        }
    }
    return false;
}

int main() {
    while(scanf("%d%d%d%d", &n, &m, &l, &r) != EOF) {
        init();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                double t;
                scanf("%lf", &t);
                add(j + n, i, log(r / t));
                add(i, j + n, log(t / l));
            }
        }
        for (int i = 1; i <= n + m; ++i) {
            add(0, i, 0);
        }
        if (spfa()) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

共 1 条回复

Star

World Exhibition

// xn - x1 <= k
// x2 <= k + x1
// x2 - k >= x1

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 20010;

int ver[N], ne[N], w[N], head[N];
int tot;

bool inque[N];
int dis[N], cnt[N];

void add(int x, int y, int z) {
    ver[++tot] = y;
    w[tot] = z;
    ne[tot] = head[x];
    head[x] = tot;
}

int n, m1, m2;

bool spfa() {
    memset(cnt, 0, sizeof(cnt));
    memset(inque, 0, sizeof(inque));
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q;
    q.push(1);
    dis[1] = 0;
    inque[1] = true;
    cnt[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        inque[x] = false;
        q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int &y = ver[i];
            if (dis[y] > dis[x] + w[i]) {
                dis[y] = dis[x] + w[i];
                cnt[y] += cnt[x];
                if (cnt[y] > n - 1) {
                    return true;
                } 
                if (!inque[y]) {
                    inque[y] = true;
                    q.push(y);
                }
            }
        }
    }
    return false;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(ver, 0, sizeof(ver));
        memset(w, 0, sizeof(w));
        memset(ne, 0, sizeof(ne));
        memset(head, 0, sizeof(head));
        tot = 0;
        scanf("%d%d%d", &n, &m1, &m2);
        for (int i = 1; i <= m1; ++i) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
        }
        for (int i = 1; i <= m2; ++i) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(y, x, -z);
        }

        // spfa
        if (spfa()) printf("-1\n");
        else if (dis[n] == 0x3f3f3f3f) printf("-2\n");
        else printf("%d\n", dis[n]);
    }
    return 0;
}