HDU-3666 THE MATRIX PROBLEM

很容易发现约束条件：L<=K[i,j]*A[i]/B[j]<=U

妈呀这可是乘法啊。。。看起来貌似没法化简。。。

那么看成对数呢？

lg(L)<=lg(K[i,j])+lg(A[i])-lg(B[j])<=lg(U)

这样子就能左移右移了吧=v=

判断是否有负权回路即可。。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <deque>

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define down(i, l, r) for(int i=l; i>=r; i--)
#define N 456
#define MAX 1<<30

using namespace std;
int read()
{
	int x=0, f=1; char ch=getchar();
	while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}

struct node{int y, n; double v;} e[N*N*4]; int fir[N*2], en;
int n, m, l, u, k[N][N], c[N*2];
double d[N*2];
bool b[N*2], ans;

void Add(int x, int y, double v) { en++; e[en].y=y, e[en].v=v, e[en].n=fir[x], fir[x]=en; }

int main()
{
	while (scanf("%d %d %d %d", &n, &m, &l, &u) != EOF)
	{
		ans=1; en=0; rep(i, 1, N*2-1) fir[i]=0;
		rep(i, 1, n) rep(j, 1, m) k[i][j]=read();
		rep(i, 1, n) rep(j, 1, m) { Add(i, j+N, log(k[i][j])-log(l)); Add(j+N, i, log(u)-log(k[i][j])); }
		deque <int> q; 
		rep(i, 1, n) b[i]=1, c[i]=1, d[i]=0, q.push_back(i);
		rep(i, 1+N, m+N) b[i]=1, c[i]=1, d[i]=0, q.push_back(i);
		while (!q.empty())
		{
			int x=q.front(), o=fir[x], y=e[o].y; b[x]=0; q.pop_front();
			if (c[x] > n) { ans=0; break; }
			while (o)
			{
				if (d[y] > d[x]+e[o].v)
				{
					d[y] = d[x]+e[o].v;
					if (!b[y]) b[y]=1, c[y]++, !q.empty()&&d[y]<=d[q.front()] ? q.push_front(y) : q.push_back(y);
				}
				o=e[o].n, y=e[o].y;
			}
		}
		if (ans) printf("YES
"); else printf("NO
");
	}
	return 0;
}