Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。 最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量。一个合法的网络流方案必须满足：(1)每条边的实际流量都不超过其最大流量且非负；(2)除了源点S和汇点T之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而S点的净流出流量等于T点的净流入流量，这个值也即该网络流方案的总运输量。最大流问题就是对于给定的运输网络，求总运输量最大的网络流方案。
上图表示了一个最大流问题。对于每条边，右边的数代表该边的最大流量，左边的数代表在最优解中，该边的实际流量。需要注意到，一个最大流问题的解可能不是唯一的。 对于一张给定的运输网络，Alice先确定一个最大流，如果有多种解，Alice可以任选一种；之后Bob在每条边上分配单位花费（单位花费必须是非负实数），要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到，Bob在分配单位花费之前，已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小，而Bob希望总费用尽量大。我们想知道，如果两个人都执行最优策略，最大流的值和总费用分别为多少。
第一行三个整数N，M，P。N表示给定运输网络中节点的数量，M表示有向边的数量，P的含义见问题描述部分。为了简化问题，我们假设源点S是点1，汇点T是点N。 接下来M行，每行三个整数A，B，C，表示有一条从点A到点B的有向边，其最大流量是C。
第一行一个整数，表示最大流的值。 第二行一个实数，表示总费用。建议选手输出四位以上小数。
HINT
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #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; }