bzoj3232:圈地游戏(分数规划+spfa/最小割)

题解

  这个题真的挺不错的…两种写法都具有一定的思维难度,也可能是我比较菜没看出来,总之感觉都很喵喵…
  首先一眼就可以看出是个分数规划题,二分答案后考虑怎么check。

方法1

  因为我们要走的是一个环,很自然地可以想到分数规划中的最优比率环问题。
  但是我们会发现对于不同的走法,每条边的收益和贡献不同,所以我们强制逆时针走这个环,那收益就可以用每条列的前缀和差分来得到了,具体就是向左走收益就减去当前列的前缀和,向右走就加上,向上向下走无收益。
  其他就和最优比率环的做法一样了,判正环别扭就权值取反判负环即可。

代码1

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
using namespace std;
const int maxn=60, inf=1e9;
const double eps=1e-6;
struct poi{int too, val, cost, pre;}e[maxn*maxn<<2];
int n, m, tot, flag;
int last[maxn*maxn], hw[maxn][maxn], lw[maxn][maxn], sum[maxn][maxn];
double dist[maxn*maxn];
bool v[maxn*maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline void add(int x, int y, int z, int l){e[++tot]=(poi){y, z, l, last[x]}; last[x]=tot;}
inline int num(int x, int y){return x*(m+1)+y;}
void spfa(int x, double y)
{
	if(flag) return; v[x]=1;
	for(int i=last[x], too;i;i=e[i].pre)
	if(dist[too=e[i].too]>dist[x]-e[i].val+y*e[i].cost+eps)
	{
		if(flag || v[too]) {flag=1; return;}
		else dist[too]=dist[x]-e[i].val+y*e[i].cost, spfa(too, y);
	}
	v[x]=0;
}
inline bool check(double x)
{
	memset(v, 0, sizeof(v));
	memset(dist, 0, sizeof(dist)); flag=0;
	for(int i=0;i<(n+1)*(m+1) && !flag;i++) spfa(i, x);
	return flag;
}
int main()
{
	read(n); read(m);
	double l=0, r=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		read(sum[i][j]), r+=sum[i][j], sum[i][j]+=sum[i-1][j];
	}
	for(int i=0;i<=n;i++) for(int j=1;j<=m;j++) read(hw[i][j]);
	for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) read(lw[i][j]);
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			int x=num(i, j);
			if(i>0) add(x, num(i-1, j), 0, lw[i][j]);
			if(i<n) add(x, num(i+1, j), 0, lw[i+1][j]);
			if(j>0) add(x, num(i, j-1), -sum[i][j], hw[i][j]);
			if(j<m) add(x, num(i, j+1), sum[i][j+1], hw[i][j+1]);
		}
	}
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.3lf\n", l);
}

方法2

  有收益有代价,选了某个收益就会产生某个代价,实际上这题就是个最大权闭合图,那么就是要求个最小割来求出最小代价了。
  考虑把要选的点割在SS集,不选的点割在TT集。
  1.S1.S向所有点连边,容量为点权。
  2.2.所有相邻的点之间连边,容量为原图边权。
  3.3.在原图外加一圈点,向TT连边,容量为无穷大。
  这么连边的正确性还是很显然的,两个相邻的点间的边被割掉,那么这两个点必定被分在不同的集合,所以会产生一条边的代价,若被分在同样的集合,一定是SS到这两个点或者这两个点到TT的路径上就已经流满了,也就是这两个点在同一个集合,属于同一个联通块,所以相邻边不会产生代价。
  周围加一圈点是为了处理边界的边权,同时向TT连边容量为无穷大那就肯定被割在TT集表示不选了。
  最后答案就是正权和-最小割了。

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
using namespace std;
const int maxn=60, maxm=maxn*maxn, inf=1e9;
const double eps=1e-5;
struct poi{int too; double cf; int pre;}e[maxm<<3];
int n, m, x, y, z, s, t, tot, sum;
double ans;
int cur[maxm], last[maxm], dist[maxm], h[maxm], hw[maxn][maxn], lw[maxn][maxn], mp[maxn][maxn];
bool v[maxm];

inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline void add(int x, int y, double z){e[++tot]=(poi){y, z, last[x]}; last[x]=tot;}

inline void ins(int x, int y, double z){add(x, y, z); add(y, x, 0);}

inline int num(int x, int y){return x*(m+2)+y+1;} 

inline bool bfs(int s, int t)
{
	for(int i=0;i<=t;i++) dist[i]=-1, v[i]=0;
	v[s]=1; dist[s]=0; int front=0, rear=1; h[1]=s;
	while(front!=rear)
	{
		int now=h[++front];
		if(front==maxm-1) front=-1;
		for(int i=last[now], too;i;i=e[i].pre)
		if(!v[too=e[i].too] && e[i].cf>eps)
		{
			dist[too]=dist[now]+1;
			v[too]=1; h[++rear]=too;
			if(too==t) return 1;	
			if(rear==maxm-1) rear=-1;
		} 
	}
	return 0;
}

inline double dfs(int x, double flow)
{
	if(x==t || !flow) return flow;
	double f=0;
	for(int &i=cur[x], too;i;i=e[i].pre)
	if(dist[too=e[i].too]==dist[x]+1 && e[i].cf)
	{
		double tmp=dfs(too, min(flow-f, e[i].cf));
		e[i].cf-=tmp; e[i^1].cf+=tmp; f+=tmp;
		if(f==flow) break; 
	}
	return f;
}

inline void dinic(int s, int t)
{
	while(bfs(s, t))
	{
		memcpy(cur, last, sizeof(last));
		ans+=dfs(s, inf);
	}
}

inline bool check(double p)
{
	tot=1; memset(last, 0, sizeof(last)); ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int x=num(i, j);
			ins(s, x, mp[i][j]);
			ins(x, num(i-1, j), p*hw[i-1][j]);
			ins(x, num(i+1, j), p*hw[i][j]);
			ins(x, num(i, j-1), p*lw[i][j-1]);
			ins(x, num(i, j+1), p*lw[i][j]);
		}
	}
	for(int i=1;i<=n;i++) ins(num(i, 0), t, inf), ins(num(i, m+1), t, inf);
	for(int i=1;i<=m;i++) ins(num(0, i), t, inf), ins(num(n+1, i), t, inf);
	dinic(s, t); return sum-ans>eps;
}

int main()
{
	read(n); read(m); s=0; t=(n+2)*(m+2)+1;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(mp[i][j]), sum+=mp[i][j];
	for(int i=0;i<=n;i++) for(int j=1;j<=m;j++) read(hw[i][j]);
	for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) read(lw[i][j]);
	double l=0, r=sum/10;
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.3lf\n", l);
}