【BZOJ3597】方伯伯运椰子(分数规划,网络流)

【BZOJ3597】方伯伯运椰子(分数规划,网络流)

题解

给定了一个满流的费用流模型

如果要修改一条边,那么就必须满足流量平衡

也就是会修改一条某两点之间的路径上的所有边

同时还有另外一条路径会进行相反的修改

现在要求最大化\(\frac{X-Y}{K}\)

二分答案\(mid\)

式子变为\(X-Y-K·mid\geq 0\)

换而言之,相当于给每次修改操作额外付出一个代价\(mid\)

要使得费用+修改代价最小

对于扩容我们很好处理

对于每条边再额外连一条边

容量为\(inf\)(可以无限扩容),费用为扩容的费用,同时,每次流过还会产生一个费用

所以扩容的费用是\(b+d\)

但是压缩呢?

对于每次压缩,相当于是退流了

所以,我们给反边的费用额外增加一个压缩的费用

所以这里的费用是\(a-d\)

但是,似乎还是不会做?

我们虽然这样处理了,但是不知道怎么计算结果。

在看了天哥的博客后,我发现了这题真的很妙啊

我们先假设所有的边都被你压缩成零了,产生了一定的费用,这个可以直接算贡献。

接下来我们有两种边

一种是反压缩,我们把压缩的容量给还原,容量是边的容量,费用是\(d-a\)。

另外一种就是扩容,也就是额外新增容量,容量为\(inf\),费用\(b+d\)

再把分数规划给套上去,把每个费用都加上一个\(mid\)(反压缩是减)

这样给源点流量为原图中的流量,做一次费用流就好啦。

然后我们再来想一想我们的分数规划变成了求什么。

本来是让\(X-Y-K·mid\geq 0\)

也就是\(Y+K·mid-X\leq 0\)

因为提前压缩的时候我们已经把所有的流量贡献的费用给减掉了

也就是我们已经减过\(X\)了

所以就是最后费用流的结果+压缩所有边的费用之和要小于\(0\)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 5555
#define inf 1000000000
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
int n,m,S,T;
int U[MAX],V[MAX],A[MAX],B[MAX],C[MAX],D[MAX];
struct Line{int v,next,w;double fy;}e[50000];
int h[MAX],cnt=2;
inline void Add(int u,int v,int w,double fy)
{
e[cnt]=(Line){v,h[u],w,fy};h[u]=cnt++;
e[cnt]=(Line){u,h[v],0,-fy};h[v]=cnt++;
}
double sum,Sum;
void Build(double mid)
{
memset(h,0,sizeof(h));cnt=2;sum=0;
for(int i=1;i<=m;++i)
{
if(U[i]!=S)Add(U[i],V[i],inf,B[i]+D[i]+mid);
Add(U[i],V[i],C[i],-(A[i]-D[i]+mid));
sum+=C[i]*(A[i]-D[i]+mid);
}
}
int pe[MAX],pv[MAX];
double dis[MAX];
bool vis[MAX];
bool SPFA()
{
for(int i=1;i<=T;++i)dis[i]=1e18;
dis[S]=0;vis[S]=true;
queue<int> Q;Q.push(S);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(!e[i].w)continue;
if(dis[v]>dis[u]+e[i].fy)
{
dis[v]=dis[u]+e[i].fy;
pv[v]=u;pe[v]=i;
if(!vis[v])vis[v]=true,Q.push(v);
}
}
vis[u]=false;
}
if(dis[T]>=1e18)return false;
int flow=inf;
for(int i=T;i!=S;i=pv[i])flow=min(flow,e[pe[i]].w);
for(int i=T;i!=S;i=pv[i])e[pe[i]].w-=flow,e[pe[i]^1].w+=flow;
sum+=flow*dis[T];
return true;
}
bool check(double mid)
{
Build(mid);
while(SPFA());
return sum<0;
}
int main()
{
n=read();m=read();S=n+1;T=n+2;
for(int i=1;i<=m;++i)
U[i]=read(),V[i]=read(),A[i]=read(),B[i]=read(),C[i]=read(),D[i]=read();
double l=0,r=5e4;
while(r-l>1e-3)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.2lf\n",l);
return 0;
}

当然,还有另外一种方法

费用流上的消圈定理:

如果残余网络上还有负环,证明当前不是最优的费用流

因此,构建出残余网络之后直接检查有无负环即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 5555
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line{int v,next;int w;}e[MAX<<2];
int h[MAX],cnt=1;
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
int n,m,U,V,A,B,C,D;
double dis[MAX];
bool vis[MAX];
bool SPFA(int u,double mid)
{
vis[u]=true;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w+mid)
{
dis[v]=dis[u]+e[i].w+mid;
if(vis[v]||SPFA(v,mid))return true;
}
}
vis[u]=false;
return false;
}
bool check(double mid)
{
for(int i=1;i<=n+2;++i)dis[i]=0,vis[i]=false;
for(int i=1;i<=n+2;++i)
if(SPFA(i,mid))return true;
return false;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;++i)
{
U=read(),V=read(),A=read(),B=read(),C=read(),D=read();
Add(U,V,B+D);if(C)Add(V,U,A-D);
}
double l=0,r=5e4;
while(r-l>1e-3)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.2lf\n",l);
return 0;
}
上一篇:把git仓库从码云迁到github,及git常用命令


下一篇:学习java随笔第八篇:封装、继承、多态