我们发现对于给定的流，Bob的最优决策就是把p全部分配到流量最大的那条边上。因此Alice的最优决策就是在保证最大流的前提下使得流量最大的边流量最小。我们二分一下这个最大流量即可。注意保留小数是真的【捂脸】，因为你要流量最大的边最小，所以就有可能是小数流量，要注意控制精度。 举个例子：【来自ZYF-ZYF】，流量最大的边最小可以是2.5。
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define inf 0x3f3f3f3f #define eps 1e-8 #define ll long long #define N 110 inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int n,m,p,h[N],num=1,w[1010],mxflow=0,lev[N],cur[N]; struct edge{ int to,next;double val; }data[2010]; inline double fabs(double x){return x<0?-x:x;} inline void add(int x,int y,int val){ data[++num].to=y;data[num].next=h[x];h[x]=num;data[num].val=val; data[++num].to=x;data[num].next=h[y];h[y]=num;data[num].val=0; } inline bool bfs(){ queue<int>q;memset(lev,0,sizeof(lev)); q.push(1);lev[1]=1; while(!q.empty()){ int x=q.front();q.pop(); for(int i=h[x];i;i=data[i].next){ int y=data[i].to;if(lev[y]||fabs(data[i].val)<eps) continue; lev[y]=lev[x]+1;if(y==n) return 1;q.push(y); } }return 0; } inline double dinic(int x,double low){ if(x==n) return low;double tmp=low; for(int &i=cur[x];i;i=data[i].next){ int y=data[i].to;if(lev[y]!=lev[x]+1||fabs(data[i].val)<eps) continue; double res=dinic(y,min(tmp,data[i].val)); if(fabs(res)<eps) lev[y]=0;else tmp-=res,data[i].val-=res,data[i^1].val+=res; if(fabs(tmp)<eps) return low; }return low-tmp; } inline bool jud(double mid){ num=1;double res=0; for(int i=1;i<=m;++i){ data[++num].val=min((double)w[i],mid);data[++num].val=0; }while(bfs()){memcpy(cur,h,sizeof(h));res+=dinic(1,inf);} return fabs(res-mxflow)<eps; } int main(){ // freopen("a.in","r",stdin); n=read();m=read();p=read(); for(int i=1;i<=m;++i){ int x=read(),y=read();w[i]=read();add(x,y,w[i]); }while(bfs()){memcpy(cur,h,sizeof(h));mxflow+=dinic(1,inf);} double l=0,r=50000;printf("%d\n",mxflow); while(r-l>eps){ double mid=(l+r)/2; if(jud(mid)) r=mid; else l=mid; }printf("%.5lf\n",r*p); return 0; }