hduTHE MATRIX PROBLEM(差分约束)

时间：2022-03-21 06:02:34

题目请戳这里

题目大意：给一个n*m的矩阵，求是否存在这样两个序列：a1，a2。。。an，b1，b2，。。。，bm，使得矩阵的第i行乘以ai，第j列除以bj后，矩阵的每一个数都在L和U之间。

题目分析：比较裸的差分约束。考虑那2个序列，可以抽象出m+n个点。乘除法可以通过取对数转换为加减法。然后就可以得到约束关系：

对于矩阵元素cij，有log(L) <= log(cij) + ai - bj <= log(U)，整理可得：

ai - bj <= log(U) - log(cij)，n+j向i建边，边权log(U) - log(cij)。

bj - ai<= log(cij) - log(L)，i向n+j建边，边权log(cij) - log(L)。

设0为源点，源点到每个点建边，边权0。从源点出发找负环，存在负环无解。

求最短路一般用spfa比较高效，但是如果判断负环的话spfa就比较慢了，因为最坏情况下复杂度依然是O(m*n)的，这题如果用spfa判断一个点进队n+m次就会TLE。一个不严谨的结论是判断sqrt（n+m）次就可以了。

判断负环还有一种更高效的方法：dfs。利用dfs深度优先的特点，找到一条路就一直往下走，能很快找出负环。每次访问一个节点后标记进栈，如果访问到某个点发现已经被标记进栈了，可以直接判断负环。

详情请见代码（二合一）：

#include <iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N = 405;

const int M = 805;

const double eps = 1e-7;

double c[N][N];

int l,r,n,m,num;

double la,ra;

struct node

{

    int to,next;

    double val;

}g[10000005];

int head[M],in[M],que[M];

double dis[M];

bool flag[M];

void build(int s,int e,double v)

{

    g[num].to = e;

    g[num].next = head[s];

    g[num].val = v;

    head[s] = num ++;

}

bool instack[M];

bool dfs(int cur)

{

    if(instack[cur])

        return true;

    instack[cur] = true;

    flag[cur] = true;//visted

    int i;

    for(i = head[cur];~i;i = g[i].next)

        if(dis[cur] + g[i].val < dis[g[i].to])

        {

            dis[g[i].to] = dis[cur] + g[i].val;

            if(dfs(g[i].to))

                return true;

        }

    instack[cur] = false;

    return false;

}

bool dspfa()

{

    int i;

    memset(flag,false,sizeof(flag));

    memset(instack,false,sizeof(instack));

    for(i = 0;i <= m + n;i ++)

    {

        dis[i] = 0.0;

    }

    for(i = 1;i <= m + n;i ++)

        if(!flag[i])

            if(dfs(i))

                return true;

    return false;

}

bool spfa()

{

    int i;

    int front,rear;

    front = rear = 0;

    for(i = 0;i <= m + n;i ++)

    {

        dis[i] = 100000000.0;

        flag[i] = false;

        in[i] = 0;

    }

    dis[0] = 0;

    in[0] = 1;

    flag[0] = true;

    que[rear ++] = 0;

    while(front != rear)

    {

        int u = que[front ++];

        if(front == M)

            front = 0;

        flag[u] = false;

        for(i = head[u];~i;i = g[i].next)

        {

            if(dis[g[i].to] > dis[u] + g[i].val)

            {

                dis[g[i].to] = dis[u] + g[i].val;

                if(flag[g[i].to] == false)

                {

                    flag[g[i].to] = true;

                    in[g[i].to] ++;

                    if(in[g[i].to] > (n + m))//sqrt((double)

                        return false;

                    que[rear ++] = g[i].to;

                    if(dis[que[front]] > dis[g[i].to])

                        swap(que[front],que[rear - 1]);

                    if(rear == M)

                        rear = 0;

                }

            }

        }

    }

    return true;

}

int main()

{

    //freopen("out.txt","r",stdin);

    int i,j,x;

    while(scanf("%d",&n) != EOF)

    {

        scanf("%d%d%d",&m,&l,&r);

        la = log10((double)l);ra = log10((double)r);

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

        num = 1;

        for(i = 1;i <= n + m;i ++)

            build(0,i,0.0);

        for(i = 1;i <= n;i ++)

            for(j = 1;j <= m;j ++)

            {

                scanf("%d",&x);

                c[i][j] = log10((double)x);

                build(i,j + n,c[i][j] - la);

                build(j + n,i,ra - c[i][j]);

            }

        if(spfa())//if(!dspfa())

            puts("YES");

        else

            puts("NO");

    }

    return 0;

}

//671MS	6620K

//312MS	6616K

相关文章