题目大意：给一个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#include #include #include #include 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