首页 > 代码库 > BZOJ 3232: 圈地游戏 分数规划+判负环

BZOJ 3232: 圈地游戏 分数规划+判负环

2024-09-28 04:11:02   219人阅读

3232: 圈地游戏

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 966  Solved: 466
[Submit][Status][Discuss]

Description

DZY家的后院有一块地，由N行M列的方格组成，格子内种的菜有一定的价值，并且每一条单位长度的格线有一定的费用。
DZY喜欢在地里散步。他总是从任意一个格点出发，沿着格线行走直到回到出发点，且在行走途中不允许与已走过的路线有任何相交或触碰（出发点除外）。记这条封闭路线内部的格子总价值为V，路线上的费用总和为C，DZY想知道V/C的最大值是多少。

Input

第一行为两个正整数n,m。
接下来n行，每行m个非负整数，表示对应格子的价值。
接下来n+1行，每行m个正整数，表示所有横向的格线上的费用。
接下来n行，每行m+1个正整数，表示所有纵向的格线上的费用。
（所有数据均按从左到右，从上到下的顺序输入，参见样例和配图）

Output

 
输出一行仅含一个数，表示最大的V/C，保留3位小数。

Sample Input

3 4
1 3 3 3
1 3 1 1
3 3 1 0
100 1 1 1
97 96 1 1
1 93 92 92
1 1 90 90
98 1 99 99 1
95 1 1 1 94
1 91 1 1 89

Sample Output

1.286

HINT

 

技术分享

 

Source

jcvb提供

想法：$max(\frac{\sum D}{\sum C})$，一般都是用分数规划求。

对于一个环，某一行\列所选择的边都是偶数的。被包含的部分就像左右括号包含一样。于是这样建图：

横边：

　　①$(i,j)->(i,j+1):C_i=边花费,D_i=sum[i][j](即该列的前缀和)$

　　②$(i,j)->(i,j-1):C_i=边花费,D_i=-sum[i][j](即该列的前缀和)$

竖边：

　　①$(i,j)->(i+1,j):C_i=边花费,D_i=0$

　　②$(i,j)->(i-1,j):C_i=边花费,D_i=0$

然后判断合法，即是判断图中是否有非负环，可以权值取反后DFS_spfa求负环（这里有一个比较快的求法）。

另一个解法：考虑如果相邻的格子被同时选中，那么中间的边的费用就不会算进来了，于是变成最小割模型。

 

#include<cstdio>typedef long long ll;template<class T>inline void read(T&x){    x=0;bool f=0;char c=getchar();    while((c<‘0‘||c>‘9‘)&&c!=‘-‘)c=getchar(); if(c==‘-‘)f=1,c=getchar();    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    x=f?-x:x;}const int MAXN(60);const double eps(1e-6);int n,m,val[MAXN][MAXN],row[MAXN][MAXN],line[MAXN][MAXN],sum;double ans;struct Node{int nd,nx,v,c;}bot[MAXN*MAXN<<2];int tot,first[MAXN*MAXN];int P(int x,int y){return (x-1)*(m+1)+y;}void add(int a,int b,int v,int c){bot[++tot]=(Node){b,first[a],v,c};first[a]=tot;}void build(){    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)val[i][j]+=val[i-1][j];    for(int i=1;i<=n+1;i++)    for(int j=1;j<=m;j++)        add(P(i,j),P(i,j+1),val[i-1][j],row[i][j]),        add(P(i,j+1),P(i,j),-val[i-1][j],row[i][j]);    for(int i=1;i<=n;i++)    for(int j=1;j<=m+1;j++)        add(P(i,j),P(i+1,j),0,line[i][j]),        add(P(i+1,j),P(i,j),0,line[i][j]);}double dis[MAXN*MAXN],limt;bool vis[MAXN*MAXN],flag;void dfs(int x){    vis[x]=true;    for(int v=first[x];v;v=bot[v].nx)    if(dis[bot[v].nd]>dis[x]+bot[v].c*limt-bot[v].v+eps)    {        if(vis[bot[v].nd]){flag=true;return;};        dis[bot[v].nd]=dis[x]+bot[v].c*limt-bot[v].v;        dfs(bot[v].nd);if(flag)return;    }    vis[x]=false;}bool ok(double mid){    limt=mid; flag=false; for(int i=1;i<=(n+1)*(m+1);i++)dis[i]=vis[i]=0;    for(int i=1;i<=(n+1)*(m+1);i++)    {        dfs(i);if(flag)return true;    }    return false;}int main(){//    freopen("C.in","r",stdin);//    freopen("C.out","w",stdout);    read(n);read(m);    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)read(val[i][j]),sum+=val[i][j];    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(line[i][j]);    build();    for(double l=0,r=sum,mid;l+eps<r;)        if(ok(mid=(l+r)/2))l=mid,ans=mid;else r=mid;    printf("%.3lf",ans);    return 0;}

 

 

 

 

BZOJ 3232: 圈地游戏 分数规划+判负环


联系
我们