【BZOJ3232】圈地游戏（分数规划，网络流）

题面

BZOJ

题解

很神仙的一道题。

首先看到最大化的比值很容易想到分数规划。现在考虑分数规划之后怎么计算贡献。

首先每条边的贡献就变成了\(mid*C\)，这个显然啊。考虑一个封闭图形如何计算答案。

发现被计算入答案的边一定是一侧有一个格子被圈进去了，另外一侧的格子没有被圈进去。那么这很像一个最小割。假设格子和源点相连表示被选进了答案，和汇点相连表示在答案以外。那么很明显把一条边两侧的格子给连起来，流量为\(mid*C\)。怎么越来越像一个最大权闭合子图了。。。

那么每个点如果要和源点断开就必定会减小它自身的权值，所以\(S\)向每个格子连格子价值的边。然而忽然发现没有东西和汇点连在一起？因为没有必须不选的格子？不，显然是有的，我们有的边显然和界外相连，所以界外必须额外新建一个点，那么从界外向汇点连一条容量为\(inf\)的边表示强制不能断开，即必须不选。这样一来，拿总的点权减去最小割判定二分即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define inf 1000000000

#define MAX 55

#define MAXL MAX*MAX*4

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;double w;}e[MAXL<<1];

int h[MAX*MAX],cnt=2;

inline void Add(int u,int v,double w)

{

	e[cnt]=(Line){v,h[u],w};h[u]=cnt++;

	e[cnt]=(Line){u,h[v],w};h[v]=cnt++;

}

int n,m,tot,Sum;

int S,T,Out;

int bh[MAX][MAX],V[MAX][MAX],E1[MAX][MAX],E2[MAX][MAX];

void BuildEdge(double mid)

{

	memset(h,0,sizeof(h));cnt=2;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			Add(S,bh[i][j],V[i][j]);

	for(int j=1;j<=m;++j)Add(bh[1][j],Out,mid*E1[1][j]);

	for(int i=2;i<=n;++i)

		for(int j=1;j<=m;++j)

			Add(bh[i-1][j],bh[i][j],mid*E1[i][j]);

	for(int j=1;j<=m;++j)Add(bh[n][j],Out,mid*E1[n+1][j]);

	for(int i=1;i<=n;++i)Add(bh[i][1],Out,mid*E2[i][1]);

	for(int i=1;i<=n;++i)

		for(int j=2;j<=m;++j)

			Add(bh[i][j-1],bh[i][j],mid*E2[i][j]);

	for(int i=1;i<=n;++i)Add(bh[i][m],Out,mid*E2[i][m+1]);

}

int level[MAX*MAX],cur[MAX*MAX];

bool bfs()

{

	memset(level,0,sizeof(level));

	queue<int> Q;level[S]=1;Q.push(S);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=h[u];i;i=e[i].next)

			if(fabs(e[i].w)>1e-5&&!level[e[i].v])

				level[e[i].v]=level[u]+1,Q.push(e[i].v);

	}

	return level[T];

}

double dfs(int u,double flow)

{

	if(u==T||flow<1e-5)return flow;

	double ret=0;

	for(int &i=cur[u];i;i=e[i].next)

	{

		int v=e[i].v;double d;

		if(fabs(e[i].w)>1e-5&&level[v]==level[u]+1)

		{

			d=dfs(v,min(flow,e[i].w));

			ret+=d;flow-=d;

			e[i].w-=d;e[i^1].w+=d;

		}

	}

	if(ret<1e-5)level[u]=0;

	return ret;

}

double Dinic()

{

	double ret=0;

	while(bfs())

	{

		for(int i=S;i<=T;++i)cur[i]=h[i];

		ret+=dfs(S,inf);

	}

	return ret;

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)bh[i][j]=++tot,V[i][j]=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)Sum+=V[i][j];

	S=0;T=Out=tot+1;

	for(int i=1;i<=n+1;++i)

		for(int j=1;j<=m;++j)E1[i][j]=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m+1;++j)E2[i][j]=read();

	double l=0,r=50000;

	while(r-l>1e-5)

	{

		double mid=(l+r)/2;

		BuildEdge(mid);

		if(Sum-Dinic()>1e-5)l=mid;

		else r=mid;

	}

	printf("%.3lf\n",l);

	return 0;

}