hdu 3666 THE MATRIX PROBLEM （差分限制）

題目描述

傳送門

題目大意：給定一個最大400*400的矩陣，對于位置c[i,j]需要乘a[i]除b[j]，問是否存在合法的a,b序列使得矩陣内的每個數都在[L,R]的區間内

題解

L<=c[i,j]∗a[i]/b[j]<=U

b[j]<=c[i,j]La[i],a[i]<=Uc[i,j]∗b[j]

對于乘法運算其實我們可以取對數之後變成加減運算。

那麼這道題隻要用spfa 求最短路判斷是否存在負環即可。

這道題的時限有點卡，是以不能保證入隊n+m次，因為資料比較弱，是以入隊 n√+m 次即可。

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define N 400003
#define inf 1000000000
using namespace std;
int point[N],nxt[N],v[N],can[N],cnt[N],tot,n,m;
double dis[N],c[N],L,U;
void add(int x,int y,double t)
{
    tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=t;
}
int spfa()
{
    for (int i=;i<=n+m;i++) dis[i]=inf,can[i]=,cnt[i]=;
    queue<int> p; p.push(); can[]=cnt[]=; dis[]=;
    int mn=sqrt((n+m)*);
    while (!p.empty()) {
        int now=p.front(); p.pop();
        for (int i=point[now];i;i=nxt[i])
          if (dis[v[i]]>dis[now]+c[i]) {
            dis[v[i]]=dis[now]+c[i];
            if (!can[v[i]]) {
                can[v[i]]=;
                cnt[v[i]]++;
                if (cnt[v[i]]>mn) return -;
                p.push(v[i]);
              }
          }
          can[now]=;
    }
    return ;
}
int main()
{
    freopen("a.in","r",stdin);
    while (scanf("%d%d%lf%lf",&n,&m,&L,&U)!=EOF) {
        tot=; L=log(L),U=log(U);
        memset(point,,sizeof(point));
        for (int i=;i<=n;i++)
         for (int j=;j<=m;j++) {
            double x; scanf("%lf",&x);
            x=log(x);
            add(j+n,i,x-L);
            add(i,j+n,U-x);
         }
        if (spfa()==-) printf("NO\n");
        else printf("YES\n");
    }
}