本文共 1432 字，大约阅读时间需要 4 分钟。

$logL<=log{C}_{ij}+log{a}_i-log{b}_j<=logR$

$s_i>=logL-log{C}_{ij}+s_{n+j}$

$s_{n+j}>=log{C}_{ij}-logR+s_i$

跑最长路即可

然后因为会超时,我把负环条件变小了一点…

其实是因为数据水,这样是不对的…还是要去学优化啊…

#include 
   
    using namespace std;const int maxn = 8e5+10;const int inf = 1e9;int n,m;double L,R,a[409][409];struct edge{
   	int to,nxt; double w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,double w){
   	d[++cnt] = (edge){
    v,head[u],w },head[u] = cnt;}double dis[maxn];int vis[maxn],shu[maxn],kl;bool spfa(int s){
   	for(int i=0;i<=n+m;i++)	dis[i] = -inf,vis[i] = shu[i] = 0;	queue
    
     q; q.push( s ); dis[s] = 0;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		vis[u] = 0;		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( dis[v]
     
      =kl )	return false;				}			}		}	}	return true;}int main(){
   	while( cin >> n >> m >> L >> R )	{
   		L = log(L), R = log(R);		for(int i=1;i<=n;i++)		for(int j=1;j<=m;j++)		{
   			scanf("%lf",&a[i][j] );			a[i][j] = log( a[i][j] );			add( n+j,i,L-a[i][j] );			add( i,n+j,a[i][j]-R );		}		for(int i=1;i<=n+m;i++)	add(0,i,0);		kl = sqrt(n+m+100);		if( spfa(0) )	cout << "YES\n";		else	cout << "NO\n";		cnt = 1;		for(int i=0;i<=n+m;i++)	head[i] = 0;	}}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110004086 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！