https://www.lydsy.com/JudgeOnline/problem.php?id=3130
本来找费用流的题，权当复习一下网络流好了。
有点麻烦的是double，干脆判断大小或者二分增加下限都用eps=1e-8操作好了（毕竟只要求精确到4位）。
我普通最大流都快忘了，板子写错了一次超时了。
网络流板子的细节要记清楚：1.增广的时候访问完哪个点就把dep标记改为-1防止同一次增广再次访问。2.往下层传递的时候用val-cnt而不是val。3.cnt=val时及时返回。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
const double eps=1e-;
int n,m,p;double mx;
struct nod{
int y,rev,next;double v,v1;
}e[maxn*];
int head[maxn]={},tot=;double Ans=;
int num[maxn]={},vis[maxn*]={};
queue<int>q;
void init(int x,int y,double v){
e[++tot].y=y;e[tot].v=v;e[tot].rev=tot+;e[tot].next=head[x];head[x]=tot;
e[++tot].y=x;e[tot].v=;e[tot].rev=tot-;e[tot].next=head[y];head[y]=tot;
}
bool fir(){
memset(num,-,sizeof(num));
q.push();num[]=;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].next){
if(e[i].v1<eps)continue;
if(num[e[i].y]==-){
num[e[i].y]=num[x]+;
q.push(e[i].y);
}
}
}
return num[n]!=-;
}
double dfs(int x,double val){
if(x==n)return val;
double cnt=,z;
for(int i=head[x];i;i=e[i].next){
if((e[i].v1<eps)||num[e[i].y]!=num[x]+)continue;
z=dfs(e[i].y,min(val-cnt,e[i].v1));
cnt+=z; e[i].v1-=z; e[e[i].rev].v1+=z;
if(val-cnt<eps)return cnt;
}num[x]=-;
return cnt;
}
bool Check(double shu){
mx=shu;double cnt=;
for(int i=;i<tot;i+=)e[i].v1=min(mx,e[i].v);
for(int i=;i<=tot;i+=)e[i].v1=;
while(fir()){
cnt+=dfs(,);
}
return Ans-cnt<eps;
}
double erfen(double mx){
double l=,r=mx;
while(r-l>eps){
double mid=(l+r)/;
if(Check(mid))r=mid;
else l=mid+eps;
}
return l;
}
int main(){
scanf("%d%d%d",&n,&m,&p);
int x,y,z;
for(int i=;i<=m;i++){scanf("%d%d%d",&x,&y,&z);init(x,y,(double)z);mx=max(mx,(double)z);}
for(int i=;i<=tot;i++)e[i].v1=e[i].v;
while(fir())Ans+=dfs(,mx);
if(Ans==){
printf("0\n0.0000\n");
}
else{
printf("%.0f\n",Ans);
printf("%.4lf\n",erfen(mx)*(double)p);
}
return ;
}