首先二分答案（dinkelbach？不知道行不行），然後就變成判斷是否可行了。
這裡有一個比較巧妙的方法，就是給圈地定一個方向，不妨為逆時針，那麼向上走就相當于把它左邊的加入答案；向下走就相當于把它左邊的從答案中減去，然後判斷是否存在負權回路即可。
另外還可以網絡流建圖，所有塊從S連邊容量為價值，然後在外面加一圈向T連邊容量為邊權inf，然後任意兩個相鄰的塊（包括外面一圈）連雙向邊容量為邊的費用。然後跑最小割從答案中減去即可。
AC代碼如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 55
#define M 100005
using namespace std;
int m,n,cnt,h[M+5][2],s[N][N],mp[N][N][4],num[N][N];
double d[N][N],len[N][N][4]; bool bo[N][N];
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};//0上 1下 2左 3右
bool ok(double t){
int i,j,k,x,y;
for (i=0; i<=m; i++)
for (j=0; j<=n; j++)
for (k=0; k<4; k++){
x=i+dx[k]; y=j+dy[k];
if (x>=0 && x<=m && y>=0 && y<=n){
len[i][j][k]=mp[i][j][k]*t;
if (!k) len[i][j][k]-=s[i][j]; else
if (k==1) len[i][j][k]+=s[i+1][j];
}
}
int head=0,tail=cnt,u=0,v=0;
for (i=1; i<=cnt; i++){
h[i][0]=u; h[i][1]=v;
if (v<n) v++; else{ u++; v=0; }
}
memset(bo,0,sizeof(bo)); memset(num,0,sizeof(num));
while (head!=tail){
head=head%M+1; x=h[head][0]; y=h[head][1]; bo[x][y]=1;
for (i=0; i<4; i++){
u=x+dx[i]; v=y+dy[i];
if (u>=0 && u<=m && v>=0 && v<=n)
if (d[x][y]+len[x][y][i]<d[u][v]){
d[u][v]=d[x][y]+len[x][y][i];
num[u][v]=num[x][y]+1;
if (num[u][v]>cnt) return 1;
if (bo[u][v]){
bo[u][v]=0; tail=tail%M+1;
h[tail][0]=u; h[tail][1]=v;
}
}
}
}
return 0;
}
int main(){
scanf("%d%d",&m,&n); cnt=(m+1)*(n+1); int i,j,x;
for (i=1; i<=m; i++)
for (j=1; j<=n; j++){
scanf("%d",&x); s[i][j]=s[i][j-1]+x;
}
for (i=0; i<=m; i++)
for (j=1; j<=n; j++){
scanf("%d",&x);
mp[i][j][2]=mp[i][j-1][3]=x;
}
for (i=1; i<=m; i++)
for (j=0; j<=n; j++){
scanf("%d",&x);
mp[i][j][0]=mp[i-1][j][1]=x;
}
double l=0,r=m*n*100,mid;
while (l+1e-6<r){
mid=(l+r)/2;
if (ok(mid)) l=mid; else r=mid;
}
printf("%.3f\n",(l+r)/2);
return 0;
}
by lych
2016.4.13