题目大意:
题解:
首先我们看到这道题让我们最优化一个分式.
所以我们应该自然而然地想到01分数规划 首先我们考虑如何恰当地计算所有在封闭多边形内部的权值 我们可以首先假定DZY一定沿着逆时针走,然后我们发现: 我们可以对所有向右,向上的边的\(a\)值都设为在这条边的左侧的同行的价值和.\(b\)值即为经过这条边的花费 剩下的两条边对应着这两条边将价值取反即可. 我们发现把路线上所有边的\(a\)加起来除二即为围住的元素的val和 所以我们就可以直接01分数规划了.#include#include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}const int maxn = 110;const double eps = 1e-5;struct Edge{ int to,next; double dis,a,b;}G[maxn*maxn<<3];int head[maxn*maxn<<2],cnt;void add(int u,int v,double a,double b){ G[++cnt].to = v; G[cnt].next = head[u]; head[u] = cnt; G[cnt].a = a; G[cnt].b = b;}bool inq[maxn*maxn<<2];double dis[maxn*maxn<<2];#define v G[i].tobool dfs(int u){ inq[u] = true; for(int i = head[u];i;i=G[i].next){ if(dis[v] > dis[u] + G[i].dis){ dis[v] = dis[u] + G[i].dis; if(inq[v]) return true; if(dfs(v)) return true; } }inq[u] = false; return false;}#undef vint nodecnt;int id[maxn][maxn];inline bool check(double mid){ memset(inq,0,sizeof inq);memset(dis,0,sizeof dis); for(int i=1;i<=cnt;++i) G[i].dis = -(G[i].a - mid*G[i].b); for(int i=1;i<=nodecnt;++i) if(dfs(i)) return true; return false;}int sl[maxn][maxn],sr[maxn][maxn];int main(){ int n,m;read(n);read(m); for(int i=1,x;i<=n;++i){ for(int j=1;j<=m;++j){ read(x); sl[i][j] = sl[i][j-1] + x; sr[i][j] = sr[i-1][j] + x; } } for(int i=0;i<=n;++i){ for(int j=0;j<=m;++j){ id[i][j] = ++nodecnt; } } for(int i=0,x;i<=n;++i){ for(int j=1;j<=m;++j){ read(x); add(id[i][j-1],id[i][j],sr[i][j],x); add(id[i][j],id[i][j-1],-sr[i][j],x); } } for(int i=1,x;i<=n;++i){ for(int j=0;j<=m;++j){ read(x); add(id[i-1][j],id[i][j],-sl[i][j],x); add(id[i][j],id[i-1][j],sl[i][j],x); } } double l = .0,r = 1e9; while(r-l > eps){ double mid = (l+r)/2.0; if(check(mid)) l = mid; else r = mid; }printf("%.3lf\n",(l/2.0)); getchar();getchar(); return 0;}