【BZOJ 3232】圈地遊戲

題目連結

題目描述

DZY家的後院有一塊地，由N行M列的方格組成，格子内種的菜有一定的價值，并且每一條機關長度的格線有一定的費用。

DZY喜歡在地裡散步。他總是從任意一個格點出發，沿着格線行走直到回到出發點，且在行走途中不允許與已走過的路線有任何相交或觸碰（出發點除外）。記這條封閉路線内部的格子總價值為V，路線上的費用總和為C，DZY想知道V/C的最大值是多少。

Sol

分數規劃

一個封閉圖形可以在走的時候把邊權該為 原邊權 減去(加上) 這一列格子價值的字首和

可以規定向左走為正 , 向右走為負

然後就是 邊權取反+判負圈 了 (這個是真的難搞TAT)

堆棧版SPFA , 不要求最短路不要設 dis 為INF !!! 直接都相同即可

因為一個負圈必然可以找到一種走法,使得邊權一直為負(似乎是這樣) !!!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<set>
#define Set(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{
	int x=0;char ch=getchar();int t=1;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	return x*t;
}
typedef long long ll;
typedef double db;
const int N=52;
const int MAXN=N*N;
const db INF=1e9;
const db eps=1e-5;
db V[MAXN];
int n,m;
struct edge{
	int to,next;int len;db w;int id;bool flag;
}a[8*MAXN];
int head[MAXN];int cnt=0;
int S,T;
bool in[MAXN];
db dis[MAXN];
inline void add(int x,int y,int w,bool fl){a[++cnt]=(edge){y,head[x],w,0.0,0,fl};head[x]=cnt;}
bool dfs(int u)
{
	if(in[u]) return 1;
	in[u]=1;
	for(register int v,i=head[u];i;i=a[i].next){
		v=a[i].to;
		if(dis[v]>dis[u]+a[i].w){
			dis[v]=dis[u]+a[i].w;
			bool g=dfs(v);
			if(g) return 1;
		}
	}
	in[u]=0;
	return 0;
}
inline bool check(db X)
{
	for(register int i=1;i<=cnt;++i){
		if(a[i].flag==1) a[i].w=V[a[i].id]-(db)a[i].len*X;
		else a[i].w=-V[a[i].id]-(db)(a[i].len*X);
		a[i].w=-a[i].w;
	}
	Set(dis,0);Set(in,0);
	for(register int i=1;i<=T;++i) if(dfs(i)) return 1;
	return 0;
}
int main()
{
	n=read();m=read();int h=0;T=(n+1)*(m+1);S=0;
	for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) V[++h]=read();
	h=m;
	for(register int i=2;i<=n;++i) for(register int j=1;j<=m;++j) V[++h]+=V[h-m];
	h=0;V[0]=0.0;
	for(register int i=1;i<=n+1;++i)
		for(register int j=1;j<=m;++j){
			++h;register int w=read();
			add(h,h+1,w,1);a[cnt].id=max(0,h-m-i+1);
			add(h+1,h,w,0);a[cnt].id=max(0,h-m-i+1);
			if(j==m) ++h;
		}
	h=0;
	for(register int i=1;i<=n;++i){
		for(register int j=1;j<=m+1;++j){
			++h;register int w=read();
			add(h,h+m+1,w,0);add(h+m+1,h,w,0);
		}
	}
	register db l=1.0,r=250000.00,ans=0.0;
	while(r-l>=eps){
		register db mid=(l+r)/2.000;
		if(check(mid)) l=mid,ans=mid;
		else r=mid;
	}
	printf("%.3lf\n",ans);
}