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

时间:2021-12-01 17:05:11

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 ;
}