Description

DZY家的后院有一块地，由N行M列的方格组成，格子内种的菜有一定的价值，并且每一条单位长度的格线有一定的费用。

DZY喜欢在地里散步。他总是从任意一个格点出发，沿着格线行走直到回到出发点，且在行走途中不允许与已走过的路线有任何相交或触碰（出发点除外）。记这条封闭路线内部的格子总价值为V，路线上的费用总和为C，DZY想知道V/C的最大值是多少。

Input

第一行为两个正整数n,m。

接下来n行，每行m个非负整数，表示对应格子的价值。

接下来n+1行，每行m个正整数，表示所有横向的格线上的费用。

接下来n行，每行m+1个正整数，表示所有纵向的格线上的费用。

（所有数据均按从左到右，从上到下的顺序输入，参见样例和配图）

Output

 

输出一行仅含一个数，表示最大的V/C，保留3位小数。

Sample Input

3 4

1 3 3 3

1 3 1 1

3 3 1 0

100 1 1 1

97 96 1 1

1 93 92 92

1 1 90 90

98 1 99 99 1

95 1 1 1 94

1 91 1 1 89

Sample Output

1.286

HINT

 

题解：

0/1分数规划，二分mid

转化为是否存在一组解

使得∑vi-mid*∑ci<=0

即，每个格线有一个边权，每个格有权，是否能找到一个封闭的图形，使得内部和-边权和>0

发现和一般的不同的是，每个元素不是可以直接访问然后取值的。

因为还有格线和封闭起来的块的问题。

假设先不管块的值。

我们发现题目是一个从某个点出发，再回到某个点，然后判断是否有一条>0的路径。

即，图中有没有正环。

那么，块的值怎么办？

可以前缀差分！！

sum[i][j]表示，∑val[1~i][j]

对于一个横边：(i,j)->(i,j+1)，边权是：mid*c+sum[i][j]

(i,j)->(i,j-1)，边权是：mid*c-sum[i][j]

竖边就是mid*c

那么对于一个闭合封闭图形，必然可以把块的贡献看作是一列一列的。

并且，如果这是一个正环，那么存在从左下角出发往右走再绕回来，然后边权之和恰好有∑sum[i][j]-sum[i-p][j]

就差分出来格内部的权值和了。

注意，最短路的时候，为了卡精度，但是赋值时不能dis[dx][dy]=dis[x][y]+w-eps或者+eps

eps只在比较的时候用，赋值就不能用了。

 

代码：

#include
     
      using namespace std;typedef long long ll;const int N=52;const double eps=0.000001;int n,m;int val[N][N];int sum[N][N];int mv[4][2]={
   {+1,0},{-1,0},{
   0,+1},{
   0,-1}};int co[N][N][4];double dis[N][N];bool vis[N][N];int in[N][N];//ci in queuestruct node{    int has,x,y;};queue
      
       q;double mid;bool spfa(){    while(!q.empty()) q.pop();    node st;    st.has=0,st.x=0,st.y=0;    dis[0][0]=0.00;    q.push(st);    while(!q.empty()){        node now=q.front();q.pop();        vis[now.x][now.y]=0;        if(now.has>(n+1)*(m+1)+1) return true;        for(int i=0;i<4;i++){            int dx=now.x+mv[i][0],dy=now.y+mv[i][1];            if(dx<0||dx>n) continue;            if(dy<0||dy>m) continue;            double w=-1.0*mid*co[now.x][now.y][i];            if(i==2) w+=sum[now.x][now.y+1];            if(i==3) w-=sum[now.x][now.y];            if(dis[dx][dy]+0.0001
       
        (n+1)*(m+1)+1) return true;                if(!vis[dx][dy]){                    vis[dx][dy]=1;                    node tmp;                    tmp.has=now.has+1;                    tmp.x=dx,tmp.y=dy;                    q.push(tmp);                }            }        }    }    return false;}bool che(){    memset(dis,0xcf,sizeof dis);    memset(in,0,sizeof in);    memset(vis,0,sizeof vis);    if(spfa()) return true;}int main(){    scanf("%d%d",&n,&m);    int mx=0;    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            scanf("%d",&val[i][j]);            mx+=val[i][j];            sum[i][j]=sum[i-1][j]+val[i][j];        }    }int t;    for(int i=0;i<=n;i++){        for(int j=1;j<=m;j++){            scanf("%d",&t);             co[i][j-1][2]=co[i][j][3]=t;        }    }    for(int i=1;i<=n;i++){        for(int j=0;j<=m;j++){            scanf("%d",&t);            co[i-1][j][0]=co[i][j][1]=t;        }    }    double l=0.00,r=1.0*mx;    double ans;    while(r-l>eps){        mid=(l+r)/2.0;        if(che()) l=mid,ans=mid;        else r=mid;    }    printf("%.3lf",ans);    return 0;}