Description
Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。
最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量。一个合法的网络流方案必须满足：(1)每条边的实际流量都不超过其最大流量且非负；(2)除了源点S和汇点T之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而S点的净流出流量等于T点的净流入流量，这个值也即该网络流方案的总运输量。最大流问题就是对于给定的运输网络，求总运输量最大的网络流方案。
上图表示了一个最大流问题。对于每条边，右边的数代表该边的最大流量，左边的数代表在最优解中，该边的实际流量。需要注意到，一个最大流问题的解可能不是唯一的。 对于一张给定的运输网络，Alice先确定一个最大流，如果有多种解，Alice可以任选一种；之后Bob在每条边上分配单位花费（单位花费必须是非负实数），要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到，Bob在分配单位花费之前，已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小，而Bob希望总费用尽量大。我们想知道，如果两个人都执行最优策略，最大流的值和总费用分别为多少。
略一分析我们只要给流量最大的边加一个p的费用就行了啊
但是怎么找流量最大的边呢
二分啊！！
先跑出最大流然后枚举mid，如果把所有边的流量都控制在mid一下最大流不变就说明mid可行
但这是不是有点太简单了？？
认真读一遍题，发现这题甚至没有要求流量是整数！！！！
然后改成实数
然后就没了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define M 1000001
#define MP make_pair
#define TS q.top().second
#define D 1e-4
using namespace std;
int n,m,ver[M], head[M],nex[M],cnt=1,d[M],g[M],p,t,x,y,z,k,maxx,ans,cur[M];
double edge[M],e[M],s;
queue <int>q;
bool pan(double a,double b)
{
if(a>b) return (a-b)<=D;
else return b-a<=D;
}
void add(int x,int y,int z)
{
ver[++cnt]=y; nex[cnt]=head[x]; head[x]=cnt; edge[cnt]=z*1.0;
ver[++cnt]=x; nex[cnt]=head[y]; head[y]=cnt; edge[cnt]=0.0;
}
bool bfs()
{
memset(d,0,sizeof(d)); while(q.size())q.pop();
d[1]=1; q.push(1); memcpy(cur,head,sizeof(head));
while(q.size())
{
int x=q.front(); q.pop();
for(int i=head[x];i;i=nex[i])
if(edge[i] && !d[ver[i]])
{
d[ver[i]]=d[x]+1;
q.push(ver[i]);
}
}
if(d[t]) return 1;
return 0;
}
double dinic(int x,double flow)
{
if(x==t || !flow) return flow;
double re=flow, k;
for(int& i=cur[x];i && re;i=nex[i])
if(edge[i] && d[ver[i]]==d[x]+1 )
{
k=dinic(ver[i],min(re,edge[i]));
if(!k) d[ver[i]]=0;
re-=k; edge[i]-=k; edge[i^1]+=k;
}
return flow-re;
}
bool check(double x)
{
double r=0;
memcpy(edge,e,sizeof(e));
for(int i=2;i<=cnt;i++) edge[i]=min(edge[i],x);
while(bfs()) while(s=dinic(1,0x3f3f3f3f*1.0)) r+=s;
return pan(r,ans*1.0);
}
double ef(double l,double r)
{
double mid,tmp=r;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid)) tmp=mid, r=mid-1;
else l=mid+1;
}
return tmp;
}
int main()
{
scanf("%d%d%d",&n,&m,&p); t=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); maxx=max(maxx,z);
}
memcpy(e,edge,sizeof(edge));
while(bfs()) while(k=dinic(1,0x3f3f3f3f)) ans+=k;
printf("%d\n",ans);
printf("%.4lf",1.0*ef(0,maxx)*p);
}