【Codeforces 653D】Delivery Bears

  二分答案+网络流验证。

  竟然没有想到我的智商也真的是喂狗了...

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=60,maxm=510;

struct Edge {int x,y,c;}Ed[maxm];

int head[maxn],next[maxm<<1],E[maxm<<1],F[maxm<<1],Ecnt;
int n,m,k;

void Add_Edge(int x,int y,int flow) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=flow;}

int q[maxn],qtop,qtail;
int h[maxn],cur[maxn];

int BFS()
{
	q[qtop=qtail=0]=1;
	memset(h,0,sizeof(h));
	for (int i=1;i<=n;i++) cur[i]=head[i];
	h[1]=1;
	while (qtop<=qtail)
	{
		int x=q[qtop++];
		for (int i=head[x];i;i=next[i]) if (!h[E[i]] && F[i^1]) h[E[i]]=h[x]+1,q[++qtail]=E[i];
	}
	return h[n];
}

int argu;

bool DFS(int x,int flow)
{
	if (x==n) {argu=flow;return true;}
	for (int &i=cur[x];i;i=next[i]) if (h[E[i]]==h[x]+1 && F[i^1])
		if (DFS(E[i],min(flow,F[i^1])))
		{
			F[i]+=argu;F[i^1]-=argu;
			return true;
		}
	h[x]=0;
	return false;
}

int Check(double c)
{
	memset(head,0,sizeof(head));Ecnt=1;
	for (int i=1;i<=m;i++)
	{
		long long flow=(long long)((long long)Ed[i].c/c);
		if (flow>k) flow=k;
		Add_Edge(Ed[i].x,Ed[i].y,(int)flow);
	}
	int res=0;
	while (BFS()) while (DFS(1,k+1)) res+=argu;
	return res;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=m;i++) scanf("%d%d%d",&Ed[i].x,&Ed[i].y,&Ed[i].c);
	double l=0,r=1e6,mid;
	int cnt=0;
	while (cnt++<=100) if (Check(mid=(l+r)/2)>=k) l=mid;else r=mid;
	printf("%.8f\n",l*k);
	return 0;
}