本文共 2117 字，大约阅读时间需要 7 分钟。

可以发现Flubber可以就当成水算答案，只需要最后答案乘上 $v^a$ 即可。

记Flubber流量为 $F$ ，水的流量为 $W$ ，两个源点同时流的最大流为 $S$ 。考虑什么样的 $(F,W)$ 是合法的，我们可以发现一个性质：满足 $F\le Fmax,W\le Wmax,F+W\le S$ 的 $(W,F)$ 都是合法的。

证明：就是固定 $F$ ，跑初始流量为 $F$ 源点在Flubber最大流，然后在残余网络里来跑源点在水处的最大流，$W$ 一定等于 $S-F$ 。（呃呃呃我不知道怎么描述，所以略过证明。

然后在限制条件下， $F^a{W}^{1-a}$ 最大值在的 $\frac{F}{W}=\frac{a}{a-1}$ 处取到。

建一个超级源点 $SS$ ，向Flubber的源点连一条流量为 $F$ 的边， 向水的源点连一条流量为 $W$ 的边， 把流量平衡的子图拎出来，求方案就是再以Flubber的源点为源点，$F$ 为流量跑最大流，剩下的没流满的流量就是水的。

#include 
   
    #define M 1000006#define N 302using namespace std;typedef double db;const double eps=1e-7,inf=1e18;int head[N],vs,vt,tot=-1,n,m;bool tag[M];struct Edge {
   	int data,nxt; db f; 	Edge() {
   }	Edge(int a,db b,int c):data(a),f(b),nxt(c) {
   }}e[M];void add(int x,int y,db z) {
   	e[++tot]=Edge(y,z,head[x]); head[x]=tot;	e[++tot]=Edge(x,z,head[y]); head[y]=tot;}namespace Flow {
   	int d[N],cur[N];	queue
    
      q;	bool bfs() {
   		while(!q.empty()) q.pop();		memset(d,-1,sizeof(d));		d[vs]=0,cur[vs]=head[vs];		q.push(vs); int x,y;		while(!q.empty()) {
   			x=q.front(),q.pop(); 			for(int i=head[x];i!=-1;i=e[i].nxt)				if(e[i].f>eps&&d[y=e[i].data]==-1) {
   					d[y]=d[x]+1; cur[y]=head[y];					if(y==vt)return 1;					q.push(y);				}		}		return 0;	}	db dfs(int x,db mf) {
   		if(x==vt||mf
     
      mf)return now;		}		return now;	}	db maxflow(db maxx) {
   		db res=0;		while(bfs()&&maxx-res>eps) res+=dfs(vs,maxx-res);		return res;	}}int main(){
   //	freopen("test.in","r",stdin);	memset(head,-1,sizeof(head));	db v,u,a,w; int x,y,z;	scanf("%d %d %lf %lf",&n,&m,&v,&a);	for(int i=1;i<=m;i++)		scanf("%d %d %d",&x,&y,&z),add(x,y,z*1.0);	db sum=0,allx=0,ally=0;	vt=3;	vs=1,sum=allx=Flow::maxflow(inf);	vs=2,sum+=Flow::maxflow(inf);	for(int i=0;i<=tot;i+=2) {
   		u=(e[i].f+e[i^1].f)*0.5;		e[i].f=e[i^1].f=u; 	}	ally=Flow::maxflow(inf);	if(sum-ally>a*sum) w=sum-ally;	else if(allx
      
       >1]=1;//			cout<
       
        <<'\n';		}   	}	vs=1,Flow::maxflow(w);	for(int i=0;i