http://acm.hdu.edu.cn/showproblem.php?pid=3666system of difference constraints：
WA 16次，气人啊啊啊啊 啊，真心现在也不知道是哪里错了：
#include<stdio.h>
#include<string.h>
#include<math.h>
#define Max 0xfffffff
int N,M;
int que[1550000],into[805],vis[805];
double dis[805],map[805][805];
int spfa()
{
int head,tail,now,i;
memset(into,0,sizeof(into));
for (i=1; i<=N ; i++ )
que[i]=i,vis[i]=0,dis[i]=Max;
head=0;tail=N;que[0]=0;dis[0]=0.0;
while (head<=tail)
{
now=que[head++];
vis[now]=1;
into[now]++;
if (into[now]>4)
return 0;
for (i=1; i<=N ; i++ )
if (dis[now]+map[now][i]<dis[i])
{
dis[i]=dis[now]+map[now][i];
if (vis[i])
que[++tail]=i,vis[i]=0;
}
}
return 1;
}
int main()
{
int i,j;
double L,U,a;
while (scanf("%d%d%lf%lf",&N,&M,&L,&U)==4)
{
for (i=0; i<=N+M ; i++ )
for (j=0; j<=N+M ; j++ )
map[i][j]=Max;
for (i=0; i<=N+M ; i++ )
map[0][i]=0.0;
U=log(U);L=log(L);
for (i=1; i<=N ; i++ )
for (j=1; j<=M ; j++ )
{
scanf("%lf",&a);
map[j+N][i]=U-log(a);
map[i][j+N]=log(a)-L;
}
N=N+M;
puts(spfa()?"YES":"NO");
}
return 0;
}
差分约束系统，是线性规划的一种特例。得研究研究它的对偶问题是什么，嘿嘿，好东西呀！！
建立模型很重要哇！！
图论的最短路，好多东西呢，得好好学学啊，spfa是个好东西。以后要多学算法多看论文了！
spfa，可以判断负权回路哈。这个题目比较弱，4次就可以了。夜游sqrt(|v|)的，n当然是一个上界。