bzoj 3232: 圈地游戏 01分数规划

题目大意:

题解:

首先我们看到这道题让我们最优化一个分式.

所以我们应该自然而然地想到01分数规划

首先我们考虑如何恰当地计算所有在封闭多边形内部的权值

我们可以首先假定DZY一定沿着逆时针走,然后我们发现:

我们可以对所有向右,向上的边的\(a\)值都设为在这条边的左侧的同行的价值和.

\(b\)值即为经过这条边的花费

剩下的两条边对应着这两条边将价值取反即可.

我们发现把路线上所有边的\(a\)加起来除二即为围住的元素的val和

所以我们就可以直接01分数规划了.

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 110;

const double eps = 1e-5;

struct Edge{

    int to,next;

    double dis,a,b;

}G[maxn*maxn<<3];

int head[maxn*maxn<<2],cnt;

void add(int u,int v,double a,double b){

    G[++cnt].to = v;

    G[cnt].next = head[u];

    head[u] = cnt;

    G[cnt].a = a;

    G[cnt].b = b;

}

bool inq[maxn*maxn<<2];double dis[maxn*maxn<<2];

#define v G[i].to

bool dfs(int u){

    inq[u] = true;

    for(int i = head[u];i;i=G[i].next){

        if(dis[v] > dis[u] + G[i].dis){

            dis[v] = dis[u] + G[i].dis;

            if(inq[v]) return true;

            if(dfs(v)) return true;

        }

    }inq[u] = false;

    return false;

}

#undef v

int nodecnt;

int id[maxn][maxn];

inline bool check(double mid){

    memset(inq,0,sizeof inq);memset(dis,0,sizeof dis);

    for(int i=1;i<=cnt;++i) G[i].dis = -(G[i].a - mid*G[i].b);

    for(int i=1;i<=nodecnt;++i) if(dfs(i)) return true;

    return false;

}

int sl[maxn][maxn],sr[maxn][maxn];

int main(){

    int n,m;read(n);read(m);

    for(int i=1,x;i<=n;++i){

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

            read(x);

            sl[i][j] = sl[i][j-1] + x;

            sr[i][j] = sr[i-1][j] + x;

        }

    }

    for(int i=0;i<=n;++i){

        for(int j=0;j<=m;++j){

            id[i][j] = ++nodecnt;

        }

    }

    for(int i=0,x;i<=n;++i){

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

            read(x);

            add(id[i][j-1],id[i][j],sr[i][j],x);

            add(id[i][j],id[i][j-1],-sr[i][j],x);

        }

    }

    for(int i=1,x;i<=n;++i){

        for(int j=0;j<=m;++j){

            read(x);

            add(id[i-1][j],id[i][j],-sl[i][j],x);

            add(id[i][j],id[i-1][j],sl[i][j],x);

        }

    }

    double l = .0,r = 1e9;

    while(r-l > eps){

        double mid = (l+r)/2.0;

        if(check(mid)) l = mid;

        else r = mid;

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

    getchar();getchar();

    return 0;

}