BZOJ3597 SCOI2014方伯伯运椰子（分数规划+spfa）

　　即在总流量不变的情况下调整每条边的流量。显然先二分答案变为求最小费用。容易想到直接流量清空跑费用流，但复杂度略有些高。

　　首先需要知道（不知道也行？）一种平时基本不用的求最小费用流的算法——消圈法。算法基于下面的定理：如果残量网络中有负环，当前费用流一定不是最小费用流（似乎很显然？）。注意到分数规划之后，我们需要知道的只是在调整边权后的网络里，最小费用流是否可能比原来更优，于是构造出残量网络，spfa判负环即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 5010

#define M 3010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

const double eps=1E-;

int n,m,p[N],t,q[N],cnt[N];

double dis[N];

bool flag[N];

struct data{int to,nxt;double len;

}edge[M<<];

void addedge(int x,int y,double z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

int inc(int &x){x++;if (x>n+) x-=n+;return x;}

bool spfa()

{

    memset(flag,,sizeof(flag));

    memset(cnt,,sizeof(cnt));

    int head=,tail=;q[]=n-;

    for (int i=;i<=n;i++) dis[i]=;dis[n-]=;

    do

    {

        int x=q[inc(head)];flag[x]=;

        for (int i=p[x];i;i=edge[i].nxt)

        if (dis[x]+edge[i].len<dis[edge[i].to])

        {

            dis[edge[i].to]=dis[x]+edge[i].len;

            if (!flag[edge[i].to])

            {

                flag[edge[i].to]=;

                q[inc(tail)]=edge[i].to;

                cnt[edge[i].to]++;

                if (cnt[edge[i].to]>=n) return ;

            }

        }

    }while (head!=tail);

    return ;

}

bool check(double k)

{

    for (int i=;i<=t;i++) edge[i].len+=k;

    bool ans=spfa();

    for (int i=;i<=t;i++) edge[i].len-=k;

    return ans;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3597.in","r",stdin);

    freopen("bzoj3597.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read()+,m=read();

    for (int i=;i<=m;i++)

    {

        int x=read(),y=read(),a=read(),b=read(),c=read(),d=read();

        addedge(x,y,b+d);

        if (c>) addedge(y,x,a-d);

    }

    double l=eps,r=,ans;

    while (l+eps<r)

    {

        double mid=(l+r)/;

        if (check(mid)) ans=mid,l=mid+eps;

        else r=mid-eps;

    }

    printf("%.2f",ans);

    return ;

}

巴特西

BZOJ3597 SCOI2014方伯伯运椰子（分数规划+spfa）

最新文章

热门文章