美叶设计网站,个人工作室注册流程及费用,深圳互动网站建设,阿里云专有网络做网站正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid3666 题目大意
一个n∗mn*mn∗m的矩阵CCC求有没有一个长度为nnn的aaa序列和一个长度为mmm的bbb序列使得 L≤Ci,j∗ai/bi≤RL\leq C_{i,j}*a_i/b_i\leq RL≤Ci,j∗ai/bi≤R 解题思路
首先我们将乘除转换为自然…正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid3666 题目大意
一个n∗mn*mn∗m的矩阵CCC求有没有一个长度为nnn的aaa序列和一个长度为mmm的bbb序列使得 L≤Ci,j∗ai/bi≤RL\leq C_{i,j}*a_i/b_i\leq RL≤Ci,j∗ai/bi≤R 解题思路
首先我们将乘除转换为自然对数。 所以要求变为 log(L)≤log(ci,j)log(ai)−log(bi)≤log(R)log(L)\leq log(c_{i,j})log(a_i)-log(b_i)\leq log(R)log(L)≤log(ci,j)log(ai)−log(bi)≤log(R) 然后我们分开两段并转换为差分约束形式 log(ai)−log(bi)≥log(L)−log(ci,j)log(a_i)-log(b_i)\geq log(L)-log(c_{i,j})log(ai)−log(bi)≥log(L)−log(ci,j) andandand log(ai)−log(bi)≥−log(R)log(ci,j)log(a_i)-log(b_i)\geq -log(R)log(c_{i,j})log(ai)−log(bi)≥−log(R)log(ci,j)
然后跑差分约束 codecodecode
#includecstdio
#includecmath
#includequeue
#includecstring
#includealgorithm
using namespace std;
const int N1100;
const double inf0x3f3f3f3f;
struct node{int to,next;double w;
}a[N*N];
int n,m,ls[N],tot;
bool v[N];
double f[N],L,R;
void addl(int x,int y,double w)
{a[tot].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;
}
bool spfa()
{int cnt0;memset(v,0,sizeof(v));queueint q;for(int i1;inm10;i)f[i]inf;q.push(1);f[1]0;v[1]1;while(!q.empty()){int xq.front();v[x]0;q.pop();if(cnt2*(nm))return 0;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y]){q.push(y);v[y]1;}}}}return 1;
}
int main()
{while(scanf(%d%d,n,m)!EOF){scanf(%lf%lf,L,R);memset(ls,0,sizeof(ls));tot0;for(int i1;in;i)for(int j1;jm;j){double x;scanf(%lf,x);addl(i,jn,log2(x)-log2(L));addl(jn,i,log2(R)-log2(x));}if(spfa()) puts(YES);else puts(NO);}
}
