http://www.lydsy.com/JudgeOnline/problem.php?id=3130

题意

一个图（有重边，无自环），给定一个整数P

第一问：求1到N最大流。

第二问：Alice确定一种最大流的方案，Bob给一些边分配费用，各边的单位费用和为P；求在Bob采取最优策略的情况下，Alice如何确定最大流方案，能使得最后总费用最小。

题解

显然Bob的最优策略就是把当前流量最大的一条边加上费用P；

所以Alice就要使最大流量最小。

二分答案，要注意这题因为有重边所以答案可能为实数！

#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
const int N=201,M=2010,T=1001;
const double eps=1e-6;

int u[M],v[M],next[M],head[N];
int cur[N],d[N],vd[N],pre[N];
int n,m,p,x[T],y[T],k;
double l,r,low[N],w[M],z[T];


void add(int x,int y,double z)
{
	u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
	u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}

void rebuild(double v)
{
	memset(head,0,sizeof(head));k=1;
	for(int i=1;i<=m;i++)
		add(x[i],y[i],min(v,z[i]));
}
double solve(int s,int t,double x)
{
	rebuild(x);
	memset(d,0,sizeof(d));
	memset(vd,0,sizeof(vd));
	memset(low,0,sizeof(low));
	memset(cur,0,sizeof(cur));
	int now=s,i;double ans=0;
	low[s]=INT_MAX;vd[0]=t;
	while(d[s]<t)
	{
		for(i=head[now];i;i=next[i])
			if(w[i]>0 && d[now]==d[v[i]]+1)
				break;
		cur[now]=i;
		if(i)
		{
			pre[v[i]]=i;low[v[i]]=min(low[now],w[i]);
			now=v[i];
			if(now==t)
			{
				for(;now!=s;now=u[pre[now]])
					w[pre[now]]-=low[t],w[pre[now]^1]+=low[t];
				low[s]=INT_MAX;ans+=low[t];
			}
		}
		else
		{
			if(!--vd[d[now]]) break;
			d[now]=t;
			for(i=head[now];i;i=next[i])
				if(w[i]>0 && d[now]>d[v[i]]+1)
					d[now]=d[v[i]]+1,cur[now]=i;
			vd[d[now]]++;
			if(now!=s) now=u[pre[now]];
		}
	}
	return ans;
}




int main()
{
	scanf("%d%d%d",&n,&m,&p);
	l=r=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%lf",&x[i],&y[i],&z[i]);
		r=max(r,z[i]);
	}
	double maxflow=solve(1,n,r);
	printf("%.0lf\n",maxflow);
	int ans=0;
	while(r-l>=eps)
	{
		double mid=(l+r)/2,flow=solve(1,n,mid);
		if(maxflow-flow<=eps) r=mid-eps;
		else l=mid+eps;
	}
	printf("%.4lf\n",l*p);
}