即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[bzoj3130][Sdoi2013]费用流 二分+最大流

编程语言 youhavepeople 6℃ 0评论
本文目录
[隐藏]

1.3130: [Sdoi2013]费用流

Time Limit: 10 Sec  Memory Limit:
128 MBSec  Special Judge


[Submit][Status][Discuss]

2.Description

 Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。


    最大流问题:给定一张有向图表示运输网络,一个源点S和一个汇点T,每条边都有最大流量。一个合法的网络流方案必须满足:(1)每条边的实际流量都不超过其最大流量且非负;(2)除了源点S和汇点T之外,对于其余所有点,都满足该点总流入流量等于该点总流出流量;而S点的净流出流量等于T点的净流入流量,这个值也即该网络流方案的总运输量。最大流问题就是对于给定的运输网络,求总运输量最大的网络流方案。




  上图表示了一个最大流问题。对于每条边,右边的数代表该边的最大流量,左边的数代表在最优解中,该边的实际流量。需要注意到,一个最大流问题的解可能不是唯一的。    对于一张给定的运输网络,Alice先确定一个最大流,如果有多种解,Alice可以任选一种;之后Bob在每条边上分配单位花费(单位花费必须是非负实数),要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到,Bob在分配单位花费之前,已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小,而Bob希望总费用尽量大。我们想知道,如果两个人都执行最优策略,最大流的值和总费用分别为多少。


3.Input

    第一行三个整数N,M,P。N表示给定运输网络中节点的数量,M表示有向边的数量,P的含义见问题描述部分。为了简化问题,我们假设源点S是点1,汇点T是点N。


    接下来M行,每行三个整数A,B,C,表示有一条从点A到点B的有向边,其最大流量是C。


4.Output

第一行一个整数,表示最大流的值。


第二行一个实数,表示总费用。建议选手输出四位以上小数。


5.Sample Input

3 2 1


1 2 10


2 3 15

6.Sample Output

10


10.0000


HINT

#include
#include
#include
#include
#include
#define INF 0x7fffffff
using namespace std;
const int N = 205;
int last[N],S,T,n,m,h[N],q[N],cnt=1;
double maxn,p,ans,lim=1e-6,vv[N*N];
struct Edge{
 int to,next; double v;
}e[N*N];
void insert( int u, int v, double w ){
 e[++cnt].to = v; e[cnt].next = last[u]; e[cnt].v = w; last[u] = cnt;
 e[++cnt].to = u; e[cnt].next = last[v]; e[cnt].v = 0; last[v] = cnt;
}
bool bfs(){
 memset(h,-1,sizeof(h));
 int tail = 1, head = 0;
 q[0] = 1; h[1] = 0;
 while( tail != head ){
  int now = q[head++];
  for( int i = last[now]; i; i = e[i].next )
   if( h[e[i].to] == -1 && vv[i] > 0 ){
    h[e[i].to] = h[now] + 1;
    q[tail++] = e[i].to;
   }
 }
 return h[T] != -1;
}
double dfs( int x, double f ){
 double w,used=0;
 if( x == T ) return f;
 for( int i = last[x]; i; i = e[i].next )
  if( h[e[i].to] == h[x] + 1 && vv[i] > 0 ){
   w = dfs(e[i].to,min(vv[i],f-used));
   vv[i] -= w; vv[i^1] += w; used += w;
   if( fabs(used-f) <= lim ) return used; 
  }
 if( used == 0 ) h[x] = -1;
 return used;
}
void dinic(){
 while( bfs() ){
  ans += dfs(S,INF);
 }
}
bool check( double li ){
 double ans1 = 0; for( int i = 1; i <= cnt; i++ ) vv[i] = min(e[i].v,li);
 while( bfs() ){
  ans1 += dfs(S,INF);
 }
 return fabs(ans1-ans) < lim;
}
int main(){
 scanf("%d%d%lf", &n, &m, &p); maxn = -INF;
 for( int i = 1,u,v; i <= m; i++ ){
  double w;
  scanf("%d%d%lf", &u, &v, &w);
  insert( u, v, w );
  maxn = max(maxn,w);
 } S = 1; T = n;
 for( int i = 1; i <= cnt; i++ ) vv[i] = e[i].v;
 dinic();
 printf("%.0lf\n", ans);
 double l = 0, r = maxn;
 while( r - l > lim ){
  double mid = (r+l) * 0.5;
  if( check(mid) ) r = mid;
  else l = mid;
 }
 printf("%.5lf", (double)l*p);
 return 0;
}


转载请注明:CodingBlog » [bzoj3130][Sdoi2013]费用流 二分+最大流

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情