[차분 제약] hdoj 3666: THE MATRIX PROBLEM

대체로 제목:
    n * m 의 행렬 맵 과 두 개의 숫자 L, U 를 드 립 니 다.이러한 수열 a [1 ~ n], b [1 ~ m] 가 존재 하 는 지 확인 하 십시오.모든 맵 [i] [j] 에 맵 [i] [j] * a [i] / b [j] 가 L 보다 크 고 U 보다 작 습 니 다.
 
대체적인 사고방식:
    log 연산 으로 곱셈 을 덧셈 으로 바 꾸 어 부등식 을 구하 다.그리고 차분 제약 을 한다.또 주의해 야 할 것 은 점 당 입단 횟수 가 n 보다 많 으 면 시간 을 초과 할 수 있다 는 점 이다.
 
 
소인 블 로그 에서 다음 두 가지 방법 을 보 세 요.
1: 어느 지점 의 입단 횟수 가 sqrt (N) 보다 많 을 때
2: 모든 입단 횟수 가 T * (N + M) 보다 많 고 그 중에서 T 는 보통 2 를 취한 다.
여기 쓰 는 게 첫 번 째 야.
 
 

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=2050;
const int mMax=1000050;
const int inf=1<<28;
struct{
    int u,v, next;
    double  w;
}edge[mMax];
int n, k, head[nMax];
double dis[nMax];
int que[nMax],m,sum[nMax];
bool vis[nMax];

void addedge(int a,int b,double w){
    edge[k].w = w;
    edge[k].u=a;
    edge[k].v=b;
    edge[k].next=head[a];
    head[a]=k;k++;
}

bool spfa(int s){      //  ，  ，   
    int i, hhead = 0, tail = 1;    //                             
    for(i = 0; i <= n; i ++){
        dis[i] = inf;////////////
        vis[i] = false;
    }
    dis[s] = 0;
    que[0] = s;
    vis[s] = true;
    while(tail != hhead){     //        。
        int u = que[hhead];
        vis[u] = false;
        for(int p = head[u]; p != 0; p = edge[p].next){
            int v = edge[p].v;     //     edge[k].v，WA   。
            if(dis[v] > dis[u] + edge[p].w){
                dis[v] = dis[u] + edge[p].w;
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == nMax) tail = 0;
                    if(++sum[v] >sqrt(n)) return false;     //          。
                }
            }
        }
        hhead ++;
        if(hhead == nMax) hhead = 0;
    }
    return true;
}

int map[403][403];
int main(){
    int m,i,j,a,b,l,u,c,s;
    char str[20];
    while(scanf("%d%d%d%d",&a,&b,&l,&u)!=EOF){
        k=1;
        memset(head,0,sizeof(head));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=a;i++){
            for(j=1;j<=b;j++){
                scanf("%d",&map[i][j]);
            }
        }
        n=a+b;
        s=n+2;      //s           “   ”
        for(i=1;i<=n;i++){
            addedge(s,i,0);
        }
        for(i=1;i<=a;i++){
            for(j=1;j<=b;j++){
                addedge(i,j+a,log(map[i][j]*1.0)-log(l*1.0));
                addedge(j+a,i,log(u*1.0)-log(map[i][j]*1.0));
            }
        }
        if(spfa(s)){
            printf("YES
");
        }
        else{
            printf("NO
");
        }
    }
    return 0;
}