首页 > 代码库 > BZOJ 3130 [Sdoi2013]费用流
BZOJ 3130 [Sdoi2013]费用流
3130: [Sdoi2013]费用流
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
第一行一个整数，表示最大流的值。 第二行一个实数，表示总费用。建议选手输出四位以上小数。
Sample Input
Sample Output
HINT
【样例说明】
对于Alice，最大流的方案是固定的。两条边的实际流量都为10。
对于Bob，给第一条边分配0.5的费用，第二条边分配0.5的费用。
总费用 为：10*0.5+10*0.5=10。可以证明不存在总费用更大的分配方案。
【数据规模和约定】
对于20%的测试数据：所有有向边的最大流量都是1。
对于100%的测试数据：N < = 100，M < = 1000。
对于l00%的测试数据：所有点的编号在I..N范围内。1 < = 每条边的最大流量 < = 50000。1 < = P < = 10。给定运输网络中不会有起点和终点相同的边。
长春亚泰（National Night）说，这道题写着费用流的题目，穿着博弈论的外衣，还请出来了Alice和Bob两哥们儿，试图用样例说明卡你智商，最终发现就只是考你反应的题。
很容易发现，最大流的值是固定的，p值是一定的，但对于Alice的方案，Bob最后的总费用就只能是图中流量最大的弧的流量*所谓的p值。所以Alice就需要让图中流量最大的弧的流量最小。
怎么办呢？长春亚泰又说：
显然需要二分来解决。
但我当时并没有想到，试图真的去用费用流那套理论来解决问题，我好菜啊。怎么办呢？长春亚泰又说：
每次让每条边的流量上限与二分值取min，判定一下这样能否流出最大流即可。
啊啊啊啊啊。于是这样，似乎就可以交了。于是我WA了。怎么回事！！！最后发现：
注意小数网络流的精度问题
为什么啊？因为如果要相对均分，那么一均，小数就出来了。EPS，EPS，EPS，能开double全开double，AC！
1 /************************************************************** 2 Problem: 3130 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:84 ms 7 Memory:872 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 using namespace std; 14 template<class T>inline void readin(T &res) { 15 static char ch; 16 while((ch=getchar())<‘0‘||ch>‘9‘); 17 res=ch-48;while((ch=getchar())>=‘0‘&&ch<=‘9‘)res=(res<<1)+(res<<3)+ch-48; 18 } 19 20 const int N = 110; 21 const int M = 2010; 22 const double eps = 1e-6; 23 struct Edge{int v,upre;double cap,flow;}g[M]; 24 int head[N], ne=-1; 25 inline void adde(int u,int v,double cap) { 26 g[++ne]=(Edge){v,head[u],cap,0},head[u]=ne; 27 g[++ne]=(Edge){u,head[v],0,0},head[v]=ne; 28 } 29 30 int n, m, s, t, p, ok; 31 int q[N], front, rear, d[N], cur[N]; 32 bool BFS(double Bound) { 33 memset(d, 0,sizeof(d)); 34 front=rear=0;d[s]=1;q[rear++]=s; 35 while(front!=rear) { 36 int u=q[front++]; 37 for( int i = head[u]; i!=-1; i = g[i].upre ) { 38 int v=g[i].v;if(ok) g[i].flow=0,g[i^1].flow=0; 39 if(!d[v]&&min(Bound,g[i].cap)>g[i].flow+eps) d[v]=d[u]+1,q[rear++]=v; 40 } 41 } 42 ok=0; 43 return d[t]>0?1:0; 44 } 45 double DFS(int u,double a,double Bound) { 46 if(u==t||a==0) return a; 47 double flow=0, f; 48 for( int &i = cur[u]; i!=-1; i = g[i].upre ) { 49 int v=g[i].v; 50 if(d[v]==d[u]+1&&(f=DFS(v,min(a,min(Bound,g[i].cap)-g[i].flow),Bound))>eps) { 51 flow+=f;a-=f;g[i].flow+=f;g[i^1].flow-=f; 52 if(a==0) return flow; 53 } 54 } 55 if(!flow) d[u]=0; 56 return flow; 57 } 58 double maxflow(double Bound) { 59 double flow=0; 60 while(BFS(Bound)) { 61 memcpy(cur, head,sizeof(head)); 62 flow+=DFS(s,0x3f3f3f3f,Bound); 63 } 64 return flow; 65 } 66 67 int main() { 68 memset(head, -1,sizeof(head)); 69 readin(n);readin(m);readin(p); 70 double CMP, lf=0, rg=0; 71 for( int i = 1; i <= m; i++ ) { 72 int u, v;double cap; 73 readin(u);readin(v);scanf("%lf",&cap); 74 rg=max(rg,cap); 75 adde(u,v,cap); 76 } 77 s=1;t=n; 78 CMP=maxflow(0x3f3f3f3f); 79 while(lf+eps<rg) { 80 double mid=(lf+rg)/2; 81 ok=1;double tmp=maxflow(mid); 82 if(tmp<CMP) lf=mid; 83 else rg=mid; 84 } 85 printf("%.lf\n%.4lf\n",CMP,lf*p); 86 return 0; 87 }
BZOJ 3130 [Sdoi2013]费用流