【BZOJ3232】圈地游戏

  网络流，最小割模型。

  从S向每个点连一条容量为该点价值的边，边界上的点向T连一条容量为该点在边界上的边权和的边，相邻两点连一条容量为两点之间的边的边权的边（好绕口...）。

  就是把被圈住的格点在集合S里，其他的在集合T里。（好像说反了？）

  跑最大流就好了。

  我比较懒几条可以合并的边没有合并。

  大常数代码需要19秒，原因不明，待会儿再改。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=55,maxv=maxn*maxn;
const double inf=1e12,eps=1e-8;
 
int head[maxv],next[maxv<<5],E[maxv<<5],Ecnt,PEcnt;
double Flow[maxv<<5];
int V[maxn][maxn],ROW[maxn][maxn],COL[maxn][maxn];
int Vcnt,S,T;
int n,m,Vsum;
 
int cur[maxv];
int h[maxv];
int Q[maxv],vis[maxv],top,tail;
 
bool BFS()
{
    memset(h,0,sizeof(h));
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=T;i++) cur[i]=head[i];
    Q[top=tail=1]=S;vis[S]=1;
    while (top<=tail)
    {
        int x=Q[top++];
        for (int i=head[x];i;i=next[i]) if (!vis[E[i]] && Flow[i^1]>eps)
            Q[++tail]=E[i],vis[E[i]]=1,h[E[i]]=h[x]+1;
    }
    return h[T];
}
 
double DFS(int x,double flow)
{
    if (x==T) return flow;
    double rest=flow,nowflow=0;
    for (int &i=cur[x];i && rest>eps;i=next[i]) if (h[E[i]]==h[x]+1 && Flow[i^1]>eps)
    {
        double d=DFS(E[i],min(rest,Flow[i^1]));
        Flow[i]+=d;Flow[i^1]-=d;
        rest-=d;
        nowflow+=d;
    }
    return nowflow;
}
 
bool Check()
{
    double res=0;
    while (BFS()) res+=DFS(S,inf);
    return Vsum-res>eps;
}
 
void Add_Edge(int x,int y,int c) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;Flow[Ecnt]=0;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;Flow[Ecnt]=c;}
int p(int x,int y) {if (x==0 || x==n+1 || y==0 || y==m+1) return T;return (x-1)*m+y;}
 
int main()
{
    scanf("%d%d",&n,&m);
    S=n*m+1;T=S+1;Ecnt=1;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&V[i][j]),Add_Edge(S,p(i,j),V[i][j]),Vsum+=V[i][j];
    PEcnt=Ecnt+1;
    for (int i=1;i<=n+1;i++) for (int j=1;j<=m;j++) scanf("%d",&ROW[i][j]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m+1;j++) scanf("%d",&COL[i][j]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
    {
        Add_Edge(p(i,j),p(i-1,j),ROW[i][j]);
        Add_Edge(p(i,j),p(i+1,j),ROW[i+1][j]);
        Add_Edge(p(i,j),p(i,j-1),COL[i][j]);
        Add_Edge(p(i,j),p(i,j+1),COL[i][j+1]);
    }
    double l=0,r=250000;
    while (r-l>1e-5)
    {
        double mid=(l+r)/2.0;
        for (int i=PEcnt;i<=Ecnt;i+=2) Flow[i^1]*=mid;
        if (Check()) l=mid;else r=mid;
        for (int i=PEcnt;i<=Ecnt;i+=2) (Flow[i^1]+=Flow[i])/=mid,Flow[i]=0;
        for (int i=2;i<PEcnt;i+=2) Flow[i^1]+=Flow[i],Flow[i]=0;
    }
    printf("%.3lf",l);
    return 0;
}

  下面这份代码跑得很快但是不知道为什么WA了。本地上能过，求指正。

  发现错误了，是精度不够...原来是r-l>1e-5，改成r-l>1e-6就好了...日死BZOJ...

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=55,maxv=maxn*maxn;
const double inf=1e12,eps=1e-8;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

int head[maxv],next[maxv<<5],E[maxv<<5],Ecnt,PEcnt;
double Flow[maxv<<5],PreF[maxv<<5];
int V[maxn][maxn],ROW[maxn][maxn],COL[maxn][maxn];
int Vcnt,S,T;
int n,m,Vsum;

int cur[maxv];
int h[maxv];
int Q[maxv],vis[maxv],top,tail;

bool BFS()
{
    memset(h,0,sizeof(h));
    memset(vis,0,sizeof(vis));
    memcpy(cur,head,sizeof(cur));
    Q[top=tail=1]=S;vis[S]=1;
    while (top<=tail)
    {
        int x=Q[top++];
        for (int i=head[x];i;i=next[i]) if (!vis[E[i]] && Flow[i^1]>eps)
        {
        	Q[++tail]=E[i];
			vis[E[i]]=1;
			h[E[i]]=h[x]+1;
			if (E[i]==T) return true;
		}
    }
    return false;
}

double argu;

bool DFS(int x,double flow)
{
    if (x==T) {argu=flow;return true;}
    for (int &i=cur[x];i;i=next[i]) if (h[E[i]]==h[x]+1 && Flow[i^1]>eps)
    	if (DFS(E[i],min(flow,Flow[i^1])))
    	{
		    Flow[i]+=argu,Flow[i^1]-=argu;
		    return true;
    	}
    return false;
}

bool Check()
{
    double res=0;
    while (BFS()) while (DFS(S,inf)) res+=argu;
    return Vsum-res>eps;
}

void Add_Edge(int x,int y,int c1,int c2) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;Flow[Ecnt]=c1;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;Flow[Ecnt]=c2;}
int p(int x,int y) {if (x==0 || x==n+1 || y==0 || y==m+1) return S;return (x-1)*m+y;}

int main()
{
    scanf("%d%d",&n,&m);
    S=n*m+1;T=S+1;Ecnt=1;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) read(V[i][j]),Add_Edge(p(i,j),T,0,V[i][j]),Vsum+=V[i][j];
    PEcnt=Ecnt+1;
    for (int i=1;i<=n+1;i++) for (int j=1;j<=m;j++) read(ROW[i][j]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m+1;j++) read(COL[i][j]);
    Add_Edge(S,p(1,1),0,ROW[1][1]+COL[1][1]);
    Add_Edge(S,p(1,m),0,ROW[1][m]+COL[1][m+1]);
    Add_Edge(S,p(n,1),0,ROW[n+1][1]+COL[n][1]);
    Add_Edge(S,p(n,m),0,ROW[n+1][m]+COL[n][m+1]);
    for (int i=2;i<m;i++) Add_Edge(S,p(1,i),0,ROW[1][i]),Add_Edge(S,p(n,i),0,ROW[n+1][i]);
    for (int i=2;i<n;i++) Add_Edge(S,p(i,1),0,COL[i][1]),Add_Edge(S,p(i,m),0,COL[i][m+1]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
    {
    	if (i<n) Add_Edge(p(i,j),p(i+1,j),ROW[i+1][j],ROW[i+1][j]);
    	if (j<m) Add_Edge(p(i,j),p(i,j+1),COL[i][j+1],COL[i][j+1]);
    }
    double l=0,r=Vsum;
    memcpy(PreF,Flow,sizeof(Flow));
    while (r-l>1e-6)
    {
        double mid=(l+r)/2.0;
        for (int i=2;i<PEcnt;i++) Flow[i]=PreF[i];
        for (int i=PEcnt;i<=Ecnt;i++) Flow[i]=PreF[i]*mid;
        if (Check()) l=mid;else r=mid;
    }
    printf("%.3f",l);
    return 0;
}