【SDOI2013】bzoj3130 费用流

2023-11-07 20:19

文章标签 费用 sdoi2013 bzoj3130

本文主要是介绍【SDOI2013】bzoj3130 费用流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。
最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量。一个合法的网络流方案必须满足：(1)每条边的实际流量都不超过其最大流量且非负；(2)除了源点S和汇点T之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而S点的净流出流量等于T点的净流入流量，这个值也即该网络流方案的总运输量。最大流问题就是对于给定的运输网络，求总运输量最大的网络流方案。

上图表示了一个最大流问题。对于每条边，右边的数代表该边的最大流量，左边的数代表在最优解中，该边的实际流量。需要注意到，一个最大流问题的解可能不是唯一的。
对于一张给定的运输网络，Alice先确定一个最大流，如果有多种解，Alice可以任选一种；之后Bob在每条边上分配单位花费（单位花费必须是非负实数），要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到，Bob在分配单位花费之前，已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小，而Bob希望总费用尽量大。我们想知道，如果两个人都执行最优策略，最大流的值和总费用分别为多少。
Input
第一行三个整数N，M，P。N表示给定运输网络中节点的数量，M表示有向边的数量，P的含义见问题描述部分。为了简化问题，我们假设源点S是点1，汇点T是点N。
接下来M行，每行三个整数A，B，C，表示有一条从点A到点B的有向边，其最大流量是C。 Output
第一行一个整数，表示最大流的值。第二行一个实数，表示总费用。建议选手输出四位以上小数。

对于Bob来说一定要把所有的费用都加在流量最大的边上，所以Alice需要让流量最大的边流量最小。二分答案限制每条边最大流量然后跑最大流验证。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double oo=1e15,eps=1e-7;
int fir[310],ne[3010],to[3010],w1[3010],f[310],que[310],n,m;
double w[3010],mid=oo;
void add(int id,int u,int v,int x)
{ne[id*2]=fir[u];fir[u]=id*2;to[id*2]=v;w1[id*2]=x;ne[id*2+1]=fir[v];fir[v]=id*2+1;to[id*2+1]=u;w1[id*2+1]=0;
}
bool bfs()
{int hd,tl,u,v,i;que[1]=hd=tl=f[1]=1;for (i=2;i<=n;i++)f[i]=0;while (hd<=tl){u=que[hd++];for (i=fir[u];i;i=ne[i])if (w[i]>eps&&!f[v=to[i]]){f[v]=f[u]+1;que[++tl]=v;}}return f[n];
}
double dfs(int u,double lim)
{int i,v;double ret=0,x;if (u==n) return lim;for (i=fir[u];i&&ret+eps<lim;i=ne[i])if (w[i]>eps&&f[v=to[i]]==f[u]+1){x=dfs(v,min(lim-ret,w[i]));ret+=x;w[i]-=x;w[i^1]+=x;}if (!ret) f[u]=0;return ret;
}
double solve()
{double x,ret=0;int i;for (i=2;i<=2*m+1;i++)w[i]=min((double)w1[i],mid);while (bfs())while (x=dfs(1,oo))ret+=x;return ret;
}
int main()
{freopen("flow.in","r",stdin);freopen("flow.out","w",stdout);int i,j,u,v,x,y,p;double l,r,ans;scanf("%d%d%d",&n,&m,&p);for (i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&x);add(i,u,v,x);}r=ans=solve();l=0;while (fabs(r-l)>eps){mid=(l+r)/2;if (solve()+eps>=ans) r=mid;else l=mid;}printf("%.0f\n%.5f\n",ans,p*l);
}