@bzoj - 3130@ [Sdoi2013]费用流

小咪咪 2023-06-01 13:59 20阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

对于一张给定的运输网络，Alice先确定一个最大流，如果有多种解，Alice可以任选一种；  
之后Bob在已知Alice的方案的前提下，每条边上分配单位花费（单位花费必须是非负实数），要求所有边的单位花费之和等于P。  
总费用等于每一条边的实际流量乘以该边的单位花费，Alice希望总费用尽量小，而Bob希望总费用尽量大。如果两个人都执行最优策略，最大流的值和总费用分别为多少。

**Input**  
第一行三个整数N，M，P。N表示给定运输网络中节点的数量，M表示有向边的数量，P的含义见问题描述部分。为了简化问题，我们假设源点S是点1，汇点T是点N。  
接下来M行，每行三个整数A，B，C，表示有一条从点A到点B的有向边，其最大流量是C。

**Output**  
第一行一个整数，表示最大流的值。  
第二行一个实数，表示总费用。建议选手输出四位以上小数。

**Sample Input**  
3 2 1  
1 2 10  
2 3 15  
**Sample Output**  
10  
10.0000

**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。给定运输网络中不会有起点和终点相同的边。

## @solution@ ##

最大流随便跑跑就可以流出来。

考虑最小费用部分，首先 Bob 肯定是把所有费用全部压在流量最大的那条边，故 Alice 选择的最大流方案一定是要所有边流量的最大值尽可能小。  
最大值尽可能小，不难想到二分。我们二分出边流量的最大值 x，将边的容量 c 改为 min(c, x)，在新图上跑最大流看是否等于原图的最大流即可。

这道题启示我们有些最小化边流量的最大值可以采用二分的方法（虽然我觉得二分套网络流的复杂度很玄）。

## @accepted code@ ##

#include<cstdio> #include<queue> using namespace std; const int MAXN = 100; const int MAXM = 1000; const int MAXV = MAXN; const int MAXE = MAXM*2; const double INF = 1E9; struct FlowGraph{ struct edge{ int to; double cap, flow; edge *nxt, *rev; }edges[MAXE + 5], *adj[MAXV + 5], *ecnt; int d[MAXV + 5], vd[MAXV + 5], s, t; void clear(int n) { for(int i=0;i<=n+3;i++) d[i] = vd[i] = 0, adj[i] = NULL; ecnt = &edges[0]; } void addedge(int u, int v, double c) { edge *p = (++ecnt), *q = (++ecnt); p->to = v, p->cap = c, p->flow = 0; p->nxt = adj[u], adj[u] = p; q->to = u, q->cap = 0, q->flow = 0; q->nxt = adj[v], adj[v] = q; p->rev = q, q->rev = p; } queue<int>que; void get_dist() { for(int i=s;i<=t;i++) d[i] = t + 3; d[t] = 0; que.push(t); while( !que.empty() ) { int f = que.front(); que.pop(); vd[d[f]]++; for(edge *p=adj[f];p;p=p->nxt) if( p->rev->cap > p->rev->flow ) if( d[f] + 1 < d[p->to] ) { d[p->to] = d[f] + 1; que.push(p->to); } } } double aug(int x, double tot) { if( x == t ) return tot; double sum = 0; int mind = t + 3; for(edge *p=adj[x];p;p=p->nxt) { if( p->cap > p->flow ) { if( d[p->to] + 1 == d[x] ) { double del = aug(p->to, min(tot - sum, p->cap - p->flow)); p->flow += del, p->rev->flow -= del, sum += del; if( sum == tot || d[s] >= t + 3 ) return sum; } mind = min(mind, d[p->to]); } } if( sum == 0 ) { vd[d[x]]--; if( vd[d[x]] == 0 ) { d[s] = t + 3; return 0; } d[x] = mind + 1; vd[d[x]]++; } return sum; } double max_flow(int _s, int _t) { s = _s, t = _t; get_dist(); double flow = 0; while( d[s] < t + 3 ) flow += aug(s, INF); return flow; } }G; int a[MAXM + 5], b[MAXM + 5]; double c[MAXM + 5]; int N, M, P; double mf; bool check(double x) { G.clear(N); for(int i=1;i<=M;i++) G.addedge(a[i], b[i], min(c[i], x)); return G.max_flow(1, N) == mf; } int main() { double le = 0, ri = -INF; scanf("%d%d%d", &N, &M, &P); G.clear(N); for(int i=1;i<=M;i++) { scanf("%d%d%lf", &a[i], &b[i], &c[i]); G.addedge(a[i], b[i], c[i]); ri = max(ri, c[i]); } mf = G.max_flow(1, N); for(int i=0;i<60;i++) { double mid = (le + ri) / 2; if( check(mid) ) ri = mid; else le = mid; } printf("%.0lf\n%lf\n", mf, ri*P); }

## @details@ ##

一开始 WA 了，调了半天调不出错来，又觉得思路没有问题。

最后发现原来流量可以为小数但是我写的整数二分（所以完全没有分析为什么输出结果要保留小数）。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11396289.html