做pc端网站咨询/seo基础知识培训视频

传送门

题意：给出一个矩阵，问是否存在一行a[i]，一列b[j]，使得这个矩阵num[i][j]*a[i]/b[j]在l和u之间。

题解：根据题意列出：

然后就是差分约束板题了，但是切记注意此时w值为double型，坑了我半天，QWQ。

附上代码：

#include<bits/stdc++.h>using namespace std;const int maxn=3*410+50;
const int maxm=410*410*3+50;
const double inf=1e9+7;int n,m,v,l,u;struct edge{int v,next;double w;
};
edge edges[maxm];
int head[maxn],tot;void init()
{memset(head,-1,sizeof(head));tot=0;
}void add_edges(int u,int v,double w)
{edges[tot].v=v;edges[tot].w=w;edges[tot].next=head[u];head[u]=tot++;
}int cnt[maxn];
double dist[maxn];
bool vis[maxn];bool spfa()
{stack<int>q;for(int i=1;i<=n+m;i++){cnt[i]=0;dist[i]=-inf;vis[i]=false;}q.push(1);dist[1]=0;vis[1]=true;while(!q.empty()){int u=q.top();q.pop();vis[u]=false;++cnt[u];if(cnt[u]>n+m){return false;}for(int i=head[u];~i;i=edges[i].next){int v=edges[i].v;double w=edges[i].w;if(dist[v]<dist[u]+w){dist[v]=dist[u]+w;if(!vis[v]){vis[v]=true;q.push(v);}}}}return true;
}int main()
{while(scanf("%d%d%d%d",&n,&m,&l,&u)!=EOF){init();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&v);add_edges(j+n,i,log(1.0*l/v));add_edges(i,j+n,-log(1.0*u/v));}}if(spfa()){printf("YES\n");}else{printf("NO\n");}}return 0;
}