http://acm.hdu.edu.cn/showproblem.php?pid=3666system of difference constraints：
WA 16次，氣人啊啊啊啊 啊，真心現(xiàn)在也不知道是哪里錯了：
#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;
}
差分約束系統(tǒng)，是線性規(guī)劃的一種特例。得研究研究它的對偶問題是什么，嘿嘿，好東西呀?。?br />建立模型很重要哇?。?br />
圖論的最短路，好多東西呢，得好好學(xué)學(xué)啊，spfa是個好東西。以后要多學(xué)算法多看論文了！
spfa，可以判斷負(fù)權(quán)回路哈。這個題目比較弱，4次就可以了。夜游sqrt(|v|)的，n當(dāng)然是一個上界。