bzoj 3232 圈地游戏 —— 01分数规划+最小割建图(最大权闭合子图)

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3232

心烦意乱的时候调这道题真是...越调越气,就这样过了一晚上...

今天再认真看看,找出几处小错,就A了...

关于题解:https://www.cnblogs.com/CQzhangyu/p/6790404.html

关于最大权闭合子图:http://www.cnblogs.com/*qi/archive/2012/03/12/2391960.html

对于这道题,首先,可以01分数规划,于是问题变成二分比值后找最大答案;

把每个格子看做一个点,点之间的边权是格子边上的值*二分的比值,则割掉这条边表示两个点中选一个,那么自然一内一外,它们的交界也就成了封闭路线的边界;

把外围看做还有一圈点,于是边缘的点向汇点连外围边界的值的边;

然后源点向每个点连权值为点(格子)权的边,割这条边表示不要这个点的贡献了;

在这个图上跑最小割,总点权减去最小割就是答案;

注意 ct = 1 !边权要乘二分的比值 k !

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define eps 1e-6
#define inf 1e9
using namespace std;
int const xn=,xm=,xe=5e4;//
int n,m,s,t,w[xn][xn],sid[xn][xn][xn][xn],S,T;
int dis[xm],hd[xm],ct=,to[xe],nxt[xe],cur[xm];
int e1[xn][xn],e2[xn][xn];
double ans,c[xe],sum;
queue<int>q;
void add(int x,int y,double z)
{
to[++ct]=y; nxt[ct]=hd[x]; c[ct]=z; hd[x]=ct;
to[++ct]=x; nxt[ct]=hd[y]; c[ct]=; hd[y]=ct;
}
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return f?ret:-ret;
}
int id(int x,int y){return (x-)*m+y;}
int P(int x,int y){return (x-)*m+y;} bool bfs()
{
while(q.size())q.pop();
memset(dis,,sizeof dis);
dis[s]=; q.push(s);
while(q.size())
{
int x=q.front(); q.pop();
for(int i=hd[x],u;i;i=nxt[i])
if(!dis[u=to[i]]&&c[i]>eps)dis[u]=dis[x]+,q.push(u);
}
return dis[t];
}
double dfs(int x,double fl)
{
if(x==t)return fl;
double ret=;
for(int &i=cur[x],u;i;i=nxt[i])
{
if(dis[u=to[i]]!=dis[x]+||c[i]<=eps)continue;
double tmp=dfs(u,min(fl-ret,c[i]));
if(tmp<eps)dis[u]=;
c[i]-=tmp; c[i^]+=tmp;
ret+=tmp; if(fl-ret<eps)return ret;
}
return ret;
}
bool ck(double k)
{
memset(hd,,sizeof hd); ct=;//=1 而不是 0 !!!!!!!!!!!!!!!!!!!!!!!
s=; t=n*m+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int x=id(i,j);
add(s,x,w[i][j]);
if(i==)add(x,t,sid[i-][j][i][j]*k);
if(j==)add(x,t,sid[i][j-][i][j]*k);
if(i==n)add(x,t,sid[i][j][i+][j]*k);
if(j==m)add(x,t,sid[i][j][i][j+]*k);
int y=id(i+,j),z=id(i,j+);
if(i<n)add(x,y,k*sid[i][j][i+][j]),add(y,x,k*sid[i][j][i+][j]);
if(j<m)add(x,z,k*sid[i][j][i][j+]),add(z,x,k*sid[i][j][i][j+]);//k*!!!
}
double ans=;
while(bfs())
{
memcpy(cur,hd,sizeof hd);
ans+=dfs(,inf);
}
return sum-ans>eps;
}
int main()
{
n=rd(); m=rd(); s=; t=n*m+; double l=,r=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)w[i][j]=rd(),r+=w[i][j],sum+=w[i][j];
for(int i=;i<=n+;i++)
for(int j=;j<=m;j++)sid[i-][j][i][j]=rd();
for(int i=;i<=n;i++)
for(int j=;j<=m+;j++)sid[i][j-][i][j]=rd();
while(l-r<=eps)
{
double mid=(l+r)*0.5;
if(ck(mid))ans=mid,l=mid+eps;
else r=mid-eps;
}
printf("%.3lf\n",ans);
return ;
}
上一篇:POJ 1273 网络流(最大流)模板


下一篇:基于python创建一个简单的HTTP-WEB服务器