THE MATRIX PROBLEM
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7819 Accepted Submission(s): 2019
Problem Description
You have been given a matrix CN*M, each element E of CN*M is positive and no more than 1000, The problem is that if there exist N numbers a1, a2, … an and M numbers b1, b2, …, bm, which satisfies that each elements
in row-i multiplied with ai and each elements in column-j divided by bj, after this operation every element in this matrix is between L and U, L indicates the lowerbound and U indicates the upperbound of these elements.
Input
There are several test cases. You should process to the end of file.
Each case includes two parts, in part 1, there are four integers in one line, N,M,L,U, indicating the matrix has N rows and M columns, L is the lowerbound and U is the upperbound (1<=N、M<=400,1<=L<=U<=10000). In part 2, there are N lines, each line includes M integers, and they are the elements of the matrix.
Each case includes two parts, in part 1, there are four integers in one line, N,M,L,U, indicating the matrix has N rows and M columns, L is the lowerbound and U is the upperbound (1<=N、M<=400,1<=L<=U<=10000). In part 2, there are N lines, each line includes M integers, and they are the elements of the matrix.
Output
If there is a solution print "YES", else print "NO".
Sample Input
3 3 1 6 2 3 4 8 2 6 5 2 9
Sample Output
YES
Source
Recommend
刚开始用差分约束写的，我去，超时到最后！！！！后来找优化算法，slf跟lll都还没看，看到了深搜的SPFA
差分约束代码，别人提交的就能过，我的就超时，搞不懂，这一定不会是人品问题，对的，一定不会是！！！！！
超时代码：（应该是oj编译器问题或者就是AC的标准提高了）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXM 500000+10
#define INF 0x3f3f3f
int dis[MAXN],vis[MAXN],used[MAXN],m,n;
int head[MAXN],cnt;
double map[MAXN][MAXN];
double L,U;
struct node
{
int u,v;
double val;
int next;
}edge[MAXM];
void init()
{
memset(head,-1,sizeof(head));
memset(map,0,sizeof(map));
cnt=0;
}
void add(int u,int v,int val)
{
node E={u,v,val,head[u]};
edge[cnt]=E;
head[u]=cnt++;
}
void getmap()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lf",&map[i][j]);
add(j+n,i,log(U/map[i][j]));
add(i,j+n,-log(L/map[i][j]));
}
}
for(int i=1;i<=n+m;i++)
add(0,i,0);
}
void SPFA()
{
memset(vis,0,sizeof(vis));
memset(used,0,sizeof(used));
memset(dis,INF,sizeof(dis));
queue<int>q;
q.push(0);
dis[0]=0;
used[0]++;
vis[0]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
node E=edge[i];
if(dis[E.v]>dis[E.u]+E.val)
{
dis[E.v]=dis[E.u]+E.val;
if(!vis[E.v])
{
vis[E.v]=1;
used[E.v]++;
if(used[E.v]>(int)sqrt(1.0*n+m))
{
cout<<"NO"<<endl;
return ;
}
q.push(E.v);
}
}
}
}
cout<<"YES"<<endl;
}
int main()
{
while(scanf("%d%d%lf%lf",&n,&m,&L,&U)!=EOF)
{
init();
getmap();
SPFA();
}
return 0;
}SPFA深搜版
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
using namespace std;
const int MAX=805;
struct node
{
int v,next;
double c;
}g[MAX*MAX];
int adj[MAX];
int n,m,e;
double dis[MAX],l,u;
bool vis[MAX],inStack[MAX];
inline void add(int u,int v,double c)
{
g[e].v=v; g[e].c=c; g[e].next=adj[u]; adj[u]=e++;
}
bool spfa(int u)
{
int i,v;
if(inStack[u])
return false;
inStack[u]=true;
vis[u]=true;
for(i=adj[u];i!=-1;i=g[i].next)
{
v=g[i].v;
if(dis[v]>dis[u]+g[i].c)
{
dis[v]=dis[u]+g[i].c;
if(!spfa(v))
{
return false;
}
}
}
inStack[u]=false;
return true;
}
bool ok()
{
int i,u,v,cnt=0;
memset(vis,0,sizeof(vis));
memset(inStack,0,sizeof(inStack));
for(i=0;i<=n+m;i++)
{
dis[i]=0;
}
for(i=1;i<=n+m;i++)
{
if(!vis[i])
{
if(!spfa(i))
{
return false;
}
}
}
return true;
}
int main()
{
int i,j;
double t;
while(scanf("%d%d %lf %lf",&n,&m,&l,&u)!=EOF)
{
e=0;
memset(adj,-1,sizeof(adj));
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%lf",&t);
add(j+n,i,log(u/t));
add(i,j+n,-log(l/t));
}
}
if(ok())
puts("YES");
else
puts("NO");
}
return 0;
}