一个双向网络中有两种液体，这两种液体之间可以混合或分离。在一个容量为(c)的管道中，两者流量((f,w))满足限制(fv+wle c)，并且方向相同。分别有(f)和(w)的(1)和(2)，以及两者共同的汇点(3)。设((F,W))为从源点到汇点的流量，最大化(F^aW^{1-a})。
(nle 305)
显然可以先忽略(v)，最后再除以它。
显然如果有条边两种液体方向相反肯定是不优的。
分别从(1)和(2)出发，求出各自的最大流(F_{max},W_{max})，再从连向(1)和(2)的超级源出来，求出总的最大流(S)。有结论：对于解((F,W))，只要满足(Fle F_{max},Wle W_{max},F+Wle S)，则一定有解。
谈谈我的理解：假设从超级源连出两条边，不断调整两条边的流量，使得流量总和为(S)。
现在假如到(1)的边少了(epsilon)，到(2)的边多了(epsilon)。那么从(2)开始的新的增广路一定和从(1)开始的原增广路有交，并且不能再找出一条从(1)开始的增广路使得可以补回(1)出发的(epsilon)。
试题准备的题解的解释：有解((F_{max},S-F_{max}))和((S-W_{max},W_{max}))（可以看做增广时优先增广其中一边），可以找到(tin[0,1])，得到((F,W)=t(F_{max},S-F_{max})+(1-t)(S-W_{max},W_{max}))。
用点高中数学的知识求出最优时(F)是多少，然后还原方案。还原的时候可以先限制流量((F,W))跑一遍，得到每条边的合流量，把这个合流量变成容量，且把边定向，限制流量((F,0))跑一遍，就可以知道(f)的流量。
using namespace std;
#include <bits/stdc++.h>
#define N 305
#define INF 1000000000
int n,m;
double v,a;
struct edge{int u,v,c;} ed[N*N];
struct EDGE{
int to;
double c;
EDGE *las;
} e[N*N];
int ne;
EDGE *last[N];
void link(int u,int v,double c){
e[ne]={v,c,last[u]};
last[u]=e+ne++;
}
#define rev(ei) (e+(int((ei)-e)^1))
int T;
EDGE *cur[N];
int dis[N],gap[N],BZ;
double dfs(int x,double s){
if (x==T)
return s;
double have=0;
for (EDGE *&ei=cur[x];ei;ei=ei->las)
if (ei->c && dis[ei->to]+1==dis[x]){
double t=dfs(ei->to,min(ei->c,s-have));
ei->c-=t,rev(ei)->c+=t,have+=t;
if (have==s)
return s;
}
cur[x]=last[x];
if (!--gap[dis[x]])
BZ=0;
++dis[x];
++gap[dis[x]];
return have;
}
void build(double c1=INF,double c2=INF){
ne=0;
memset(last,0,sizeof(EDGE*)*(n+2));
for (int i=0;i<m;++i){
link(ed[i].u,ed[i].v,ed[i].c);
link(ed[i].v,ed[i].u,ed[i].c);
}
link(n+1,1,c1),link(1,n+1,0);
link(n+1,2,c2),link(2,n+1,0);
T=3;
}
double flow(int S){
memset(gap,0,sizeof gap);
memset(dis,0,sizeof dis);
gap[0]=n+1;
memset(cur,0,sizeof cur);
BZ=1;
double res=0;
while (BZ)
res+=dfs(S,INF);
return res;
}
double doit(int S,double c1=INF,double c2=INF){
build(c1,c2);
return flow(S);
}
pair<double,double> ans[N*N];
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d%lf%lf",&n,&m,&v,&a);
for (int i=0;i<m;++i){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
ed[i]={u,v,c};
}
double Fmx=doit(1);
double Wmx=doit(2);
double S=doit(n+1);
double Fmn=S-Wmx,tmp=a*S,F,W;
if (Fmn<=tmp && tmp<=Fmx)
F=tmp;
else if (tmp<Fmn)
F=Fmn;
else
F=Fmx;
W=S-F;
doit(n+1,F,W);
for (int i=0;i<m;++i){
double f=ed[i].c-e[i*2].c;
if (f>0)
e[i*2].c=f,e[i*2+1].c=0;
else
e[i*2].c=0,e[i*2+1].c=-f;
ans[i].second=f;
}
e[m*2].c=F,e[m*2+1].c=0;
e[(m+1)*2].c=e[(m+1)*2+1].c=0;
flow(n+1);
for (int i=0;i<m;++i){
double f;
if (ans[i].second>0)
ans[i].first=e[i*2+1].c;
else
ans[i].first=-e[i*2].c;
ans[i].second-=ans[i].first;
}
for (int i=0;i<m;++i)
printf("%lf %lf
",ans[i].first/v,ans[i].second);
double val=pow(F/v,a)*pow(W,1-a);
printf("%lf
",val);
return 0;
}