#include<cstdio>
#include<iostream>
#define M 10000
#define inf 0x7fffffff
#include<cstring>
#define eps 1e-5
using namespace std;
struct data
{
int x,y;
double z;
}a[M];
int d[M],q[M],S,T,cnt=,n,m,head[M],next[M],u[M];
double p,w[M],l,r,ss,ans,ans1;
void jia1(int a1,int a2,double a3)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
w[cnt]=a3;
return;
}
void jia(int a1,int a2,double a3)
{
jia1(a1,a2,a3);
jia1(a2,a1,);
return;
}
bool bfs()
{
memset(d,,sizeof(int)*(T+));
int h=,t=;
q[]=S;
d[S]=;
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(!d[u[i]]&&w[i])
{
d[u[i]]=d[p]+;
if(d[T])
return ;
t++;
q[t]=u[i];
}
}
return ;
}
double dinic(int s,double f)
{
if(s==T)
return f;
double rest=f;
for(int i=head[s];i&&rest;i=next[i])
if(w[i]&&d[u[i]]==d[s]+)
{
double now=dinic(u[i],min(rest,w[i]));
if(!now)
d[u[i]]=;
w[i]-=now;
w[i^]+=now;
rest-=now;
}
return f-rest;
}
void jian(double mi)
{
cnt=;
memset(head,,sizeof(int)*(T+));
for(int i=;i<=m;i++)
if(a[i].z<mi)
jia(a[i].x,a[i].y,a[i].z);
else
jia(a[i].x,a[i].y,mi);
return;
}
int main()
{
scanf("%d%d%lf",&n,&m,&p);
for(int i=;i<=m;i++)
{
scanf("%d%d%lf",&a[i].x,&a[i].y,&a[i].z);
jia(a[i].x,a[i].y,a[i].z);
}
S=;
T=n;
for(;bfs();)
ans+=dinic(S,inf);
printf("%d\n",(int)ans);
l=;
r=;
for(;r-l>eps;)
{
double mid=(l+r)/;
jian(mid);
ans1=;
for(;bfs();)
ans1+=dinic(S,inf);
if(ans1==ans)
{
ss=mid;
r=mid;
}
else
l=mid;
}
printf("%.4lf",ss*p);
return ;
}
贪心 BOB肯定全加在最大权值的边上，二分权值网络流。