HDU 3666 THE MATRIX PROBLEM (差分约束)

时间：2024-09-26 22:04:14

题意：给定一个最大400*400的矩阵，每次操作可以将某一行或某一列乘上一个数，问能否通过这样的操作使得矩阵内的每个数都在[L,R]的区间内。

析：再把题意说明白一点就是是否存在ai,bj，使得l<=cij*(ai/bj)<=u (1<=i<=n,1<=j<=m)成立。

首先把cij先除到两边去，就变成了l'<=ai/bj<=u'，由于差分约束要是的减，怎么变成减法呢？取对数呗，两边取对数得到log(l')<=log(ai)-log(bj)<=log(u')。

然后把ai, bj看成是两个点，那两个是权值，就可以差分约束了，但是。。这个题太坑了，会TLE，必须要判断好结束条件，就是访问次数超过sqrt(m+n),

就结束，如果不开根号，就会一直TLE。。。。有没有天理了。。。。

析：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <stack>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-10;

const int maxn = 800 + 5;

const int mod = 1e9 + 7;

const char *mark = "+-*";

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

int n, m;

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

int head[maxn], to[maxn*maxn/2], Next[maxn*maxn/2], cnt;

double w[maxn*maxn/2], l, u, d[maxn];

void addedge(int u, int v, double c){

    to[cnt] = v;

    w[cnt] = c;

    Next[cnt] = head[u];

    head[u] = cnt++;

}

int vis[maxn], num[maxn];

bool spfa(){

    memset(vis, 0, sizeof(vis));

    memset(num, 0, sizeof(num));

    fill(d, d+n+m+1, inf);

    queue<int> q;

    vis[0] = 1;  d[0] = 0;  num[0] = 1;

    q.push(0);

    int limit = sqrt(m+n+0.5);//不开根号，想AC？都到没有。

    while(!q.empty()){

        int u = q.front();  q.pop();

        vis[u] = 0;

        for(int i = head[u]; i != -1; i = Next[i]){

            int v = to[i];

            double c = w[i];

            if(!vis[v] && d[v] > d[u] + c){

                if(++num[v] > limit)  return false;

                d[v] = d[u] + c;

                q.push(v);

                vis[v] = 1;

            }

        }

    }

    return true;

}

int main(){

    while(scanf("%d %d %lf %lf", &n, &m, &l, &u) == 4){

        memset(head, -1, sizeof(head));

        cnt = 0;

        double ll = log(l);

        double uu = log(u);

        for(int i = 0; i < n; ++i){

            for(int j = 0; j < m; ++j){

                double x;

                scanf("%lf", &x);

                x = log(x);

                addedge(i, j+n, x-ll);

                addedge(j+n, i, uu-x);

            }

        }

        if(spfa())  puts("YES");

        else puts("NO");

    }

    return 0;

}

　　

相关文章