bzoj 3597: [Scoi2014]方伯伯运椰子 0/1分数规划

2021-09-01 22:16:02

3597: [Scoi2014]方伯伯运椰子

Time Limit: 30 Sec Memory Limit: 64 MB
Submit: 144 Solved: 78
[Submit][Status][Discuss]

Description

.................

Input

第一行包含二个整数N，M

接下来M行代表M条边，表示这个交通网络

每行六个整数，表示Ui,Vi,Ai,Bi,Ci,Di

接下来一行包含一条边，表示连接起点的边

Output

一个浮点数，保留二位小数。表示答案，数据保证答案大于0

Sample Input

5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22

Sample Output

103.00

HINT

1<=N<=5000

0<=M<=3000

1<=Ui,Vi<=N+2

0<=Ai,Bi<=500

0<=Ci<=10000

0<=Di<=1000

　　根本搞不懂网上的什么消圈算法，我的思路是这样的：不用想先肯定是枚举答案若ans<delta/tot,那么delta-ans*tot>0，我们先将所有有流的边假设退掉，然后将每条边分为撤销默认操作和新的扩边操作，这样可以直接通过0/1分数规划套费用流解决了，具体怎么加加减减比较烦人，可以直接参考代码。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 5100

#define MAXE MAXV*20

#define MAXV MAXN*2

#define inf 1e100

#define INF 0x3f3f3f3f

#define eps 1e-4

typedef double real;

struct Edge

{

        int np;

        int val;

        real cost;

        Edge *neg,*next;

}E[MAXE],*V[MAXV];

int tope=-;

int sour=,sink=;

void addedge(int x,int y,int v,real c)

{

//        cout<<"Add: "<<x<<" "<<y<<" "<<v<<" "<<c<<endl;

        E[++tope].np=y;

        E[tope].val=v;

        E[tope].cost=c;

        E[tope].next=V[x];

        V[x]=&E[tope];

        E[++tope].np=x;

        E[tope].val=;

        E[tope].cost=-c;

        E[tope].next=V[y];

        V[y]=&E[tope];

        V[x]->neg=V[y];

        V[y]->neg=V[x];

}

int q[MAXV*];

int vis[MAXV],vistime;

real dis[MAXV];

Edge *prve[MAXV];

int prv[MAXV];

int n,m;

bool spfa()

{

        int now=sour;

        Edge *ne;

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

                dis[i]=-inf;

        dis[now]=;

        vis[now]=++vistime;

        q[]=now;

        int head=-,tail=;

        while (head<tail)

        {

                now=q[++head];

                vis[now]=;

                for (ne=V[now];ne;ne=ne->next)

                {

                        if (ne->val && dis[ne->np]<dis[now]+ne->cost)

                        {

                                dis[ne->np]=dis[now]+ne->cost;

                                prv[ne->np]=now;

                                prve[ne->np]=ne;

                                if (vis[ne->np]!=vistime)

                                {

                                        vis[ne->np]=vistime;

                                        q[++tail]=ne->np;

                                }

                        }

                }

        }

        return dis[sink]!=-1e100;

}

pair<int,real> cost_flow()

{

        int x;

        int totf=;

        real sumc=;

        int maxf;

        while (spfa())

        {

                maxf=INF;

                for (x=sink;x!=sour;x=prv[x])

                        maxf=min(maxf,prve[x]->val);

                for (x=sink;x!=sour;x=prv[x])

                {

                        prve[x]->val-=maxf;

                        prve[x]->neg->val+=maxf;

                }

                sumc+=maxf*dis[sink];

                totf+=maxf;

        }

        return make_pair(totf,sumc);

}

struct edge

{

        int x,y,vdec,vinc,vcur,vcst;

}e[MAXE];

int main()

{

        //freopen("input.txt","r",stdin);

        int x,y,z;

        scanf("%d%d",&n,&m);

        sour=n+;

        sink=n+;

        int mxflow;

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

        {

                scanf("%d%d%d%d%d%d",&e[i].x,&e[i].y,&e[i].vdec,&e[i].vinc,&e[i].vcur,&e[i].vcst);

                if (e[i].x==sour)

                        mxflow=e[i].vcur;

        }

        double l,r,mid;

        l=,r=;

        while (l+eps<r)

        {

                memset(V,,sizeof(V));

                tope=-;

                mid=(l+r)/;

                double res=;

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

                {

                        addedge(e[i].x,e[i].y,e[i].vcur,e[i].vdec-e[i].vcst+mid);

                        addedge(e[i].x,e[i].y,mxflow-e[i].vcur,-e[i].vinc-e[i].vcst-mid);

                        res+=e[i].vcur*(-e[i].vdec+e[i].vcst-mid);

                }

                res+=cost_flow().second;

                if (res<=)

                        r=mid;

                else

                        l=mid;

        }

        printf("%.2lf\n",l);

        return ;

}

码农公寓