A：Delivery Bears
题意：给定 \(n\) 点 \(m\) 边的有向图，边有边权 \(c\)。有 \(x\) 只熊，每只熊可以携带相同重量的物品，每只熊从 \(1\) 出发把物品运到 \(n\) 处。对每条边记录共有几只熊经过，该数量乘以物品重量不能超过这条边的边权，求满足此条件的物品最大重量。
数据范围：\(2 ≤ n ≤ 50, 1 ≤ m ≤ 500, 1 ≤ x ≤ 100 000\)。
不难想到二分答案，对于二分值 \(mid\)，那么可以求出每条边最多经过的熊的数量为 \(\lfloor \frac{c}{mid}\rfloor\)，发现这就是网络流的模型。那么求出最大流判断其是否 \(\geq x\) 即可。时间复杂度 \(O(nm^2\log c)\)。
#include<bits/stdc++.h>
#define eps 1e-12
using namespace std;
typedef long long ll;
const int N=55,M=505;
int n,m,x;
struct edges{
int u,v,w;
ll val;
}e[M];
int t=1,first[N],v[M<<1],nxt[M<<1];
ll w[M<<1];
void add(int x,int y,ll val){
nxt[++t]=first[x],first[x]=t,v[t]=y,w[t]=val;
}
int f[N],d[N];
queue<int>Q;
bool bfs(){
memset(d,-1,sizeof(d));
memcpy(f,first,sizeof(first));
while(!Q.empty()) Q.pop();
Q.push(1),d[1]=0;
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=first[x];i;i=nxt[i]){
if(w[i]&&d[v[i]]==-1){
d[v[i]]=d[x]+1;
Q.push(v[i]);
}
}
}
return d[n]!=-1;
}
ll dinic(int now,ll flow){
if(now==n) return flow;
int delta,ans=0;
for(int &i=f[now];i;i=nxt[i]){
int x=v[i];
if(w[i]&&d[x]==d[now]+1){
delta=dinic(x,min(flow,w[i]));
w[i]-=delta,w[i^1]+=delta;
flow-=delta,ans+=delta;
if(!flow) return ans;
}
}
return ans;
}
bool check(double mid){
for(int i=1;i<=m;++i)
e[i].val=(ll)floor((long double)e[i].w/mid);
t=1,memset(first,0,sizeof(first));
for(int i=1;i<=m;++i){
add(e[i].u,e[i].v,e[i].val);
add(e[i].v,e[i].u,0);
}
ll ans=0;
while(bfs()) ans+=dinic(1,1e6);
return ans>=x;
}
int main(){
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
long double l=0,r=1e6;
while(r-l>eps){
long double mid=(l+r)/2;
check(mid)?l=mid:r=mid;
}
printf("%.10Lf\n",l*x);
return 0;
}