hdu 3666 THE MATRIX PROBLEM 차동 제약 조건

http://acm.hdu.edu.cn/showproblem.php?pid=3666
제목: N * M 의 행렬 을 하나 드 리 겠 습 니 다. 2 열 a1, a2, a3. an 과 b1, b2. N,M<=400
사고방식: 차분 구속.제목 에서 알 수 있 듯 이 행렬 의 모든 요소 에 만족 해 야 하 는 조건 은 L < = a [i] * m [i] [j] / b [j] < = U, 그러면 우 리 는 아래 의 두 가지 식 을 얻 을 수 있 습 니 다: L * b [j] < = a [i] * m[i][j]  a [i] * m [i] [j] <= U * b [j] 는 차이 점 제약 에서 dis [] 앞 에 계수 가 없 기 때문에 계 수 를 취소 하기 위해 우 리 는 대 식 으로 두 번 대 수 를 얻 을 수 있 습 니 다. log (b [j]) - log (a [i] < = log (m [i] [j] / L) 를 얻 을 수 있 습 니 다. 같은 이치 로 두 식 을 얻 을 수 있 습 니 다. 마지막 으로 spfa 로 마이너스 링 을 판단 하면 답 을 얻 을 수 있 습 니 다.
코드:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
const int N = 410 ;
const int inf = (1<<30) ;
int n,m,l,u;
struct node{
	int num ,nx;
	double dis ;
}edge[N*N*2] ;

int root[N*2] , cnt ;
double  dis[N*2] ;
bool vis[N*2] ;
int in[N*2] ;
std::queue<int> que ;
inline bool relax(int u ,int v ,double d){
	if(dis[v] > dis[u] + d){
		dis[v] = dis[u] + d ;
		return 1 ;
	}
	return 0 ;
}
bool spfa(){
	while(!que.empty())	que.pop() ;
	for(int i=1;i<=n;i++){
		dis[i] = inf ;
		vis[i] = 0 ;
		in[i] = 0 ;		
	}
	dis[1] = 0 ; 
	vis[1] = 1 ;
	in[1] = 1 ;
	que.push(1) ;
	while(!que.empty()){
		int u = que.front() ; que.pop() ;
		vis[u] = 0 ;
		for(int i=root[u] ;i!=-1;i=edge[i].nx){
			int v = edge[i].num ;
			double d = edge[i].dis ;
			if( 1==relax(u,v,d) && !vis[v]){
				vis[v] = 1 ;
				if(++in[v] > (int)sqrt(1.0*n))	return 0 ;		//               sqrt(n)      
				que.push(v) ;
			}
		}
	}
	return true ;	
}
void add(int a, int b, double c){
	edge[cnt].nx = root[a] ;
	edge[cnt].num = b ;
	edge[cnt].dis = c;
	root[a] = cnt++ ;
}
int main(){
	double res ,a;
	while(scanf("%d %d %d %d",&n,&m,&l,&u) == 4){
		memset(root, -1, sizeof(root));
		cnt = 0 ;
		double b,c ;
		b = log(l*1.0) ;
		c = log(u*1.0) ;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%lf",&a);
				a = log(a) ;	
				add(i,j+n,a-b) ;
				add(j+n,i,c-a) ;
			}
		}
		n = n + m ;		//       ，         
		if(spfa())	printf("YES
");
		else		printf("NO
");
	}	
	return 0 ;
}