CFgym Son of Pipe Stream【网络流+人类智慧】

CFgym Son of Pipe Stream

可以发现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 <bits/stdc++.h>
#define M 1000006
#define N 302
using 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<int> 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<eps)return mf; //流太小就掐断 int y; db fl,now=0;for(int &i=cur[x];i!=-1;i=e[i].nxt) {
    if(e[i].f<eps||d[y=e[i].data]!=d[x]+1) continue;fl=dfs(y,min(mf-now,e[i].f));now+=fl,e[i].f-=fl,e[i^1].f+=fl;if(now+eps>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<a*sum) w=allx;else w=a*sum;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; 
// cout<<e[i].f<<'\n'; }vs=1,Flow::maxflow(w);vs=2,Flow::maxflow(sum-w);for(int i=0;i<=tot;i+=2) {
    db u=e[i].f,v=e[i^1].f;if (u<=v) {
    e[i].f=(v-u)*0.5;e[i^1].f=0;
// cout<<e[i].f<<'\n';} else {
    e[i^1].f=(u-v)*0.5;e[i].f=0;tag[i>>1]=1;
// cout<<e[i^1].f<<'\n';}}vs=1,Flow::maxflow(w);for(int i=0;i<m;i++){
    
// cout<<e[2*i].f<<" "<<e[2*i+1].f<<'\n';if (!tag[i]) printf("%.10f %.10f\n",e[2*i+1].f/v,e[2*i].f);else printf("%.10f %.10f\n",-e[2*i].f/v,-e[2*i+1].f);}printf("%.10f\n",pow(w/v,a)*pow(sum-w,1.0-a));return 0;
}