题目描述
大战将至, 美国决定实行计划经济。美国西部总共有 N 个城市，编号
为 0 ∼ N − 1，以及 M 条道路，道路是单向的。其中城市 0 是一个大城
市，里面住着 K 个人，而城市 N − 1 是一个农业城市。现在所有城市 0 的
居民都需要到城市 N − 1 去领取食物。由于担心体力不支，所以居民都会
采取开车的形式出行。但道路不是无限宽的，对于一条道路，会有 ci 的限
制，表示在同一天内，最多只能有 ci 辆车同时在这条道路上行驶。一条道
路的长度为 1，每辆车的行驶速度也可以假定为 1 每天。城市 N − 1 会在
每个居民都到达后马上开始发放食物。现在 Reddington 想知道，假如在最
优安排下，居民最早能在多少天后领到食物。假如没有居民那就不需要发
放食物，默认为第 0 天。
题解
ORZ zyz
首先答案具有单调性，可以二分。
然后贪心一波，我们肯定要捡着最短路去走，然后我们增广出了一条路，因为时间时固定的，所以我们能通过的人数已经确定了。
就是(T-dis+1)*min(l)前面的是第一波人到终点到结束的时间， minl表示路径权值的最小值。
然后我们就一直重复这个过程，发现这个过程和EK费用流完全一样。
代码
#include#include #include #include #define inf 1e18#define N 1009#define M 20002using namespace std;typedef long long ll;queue q; int dis[N],head[N],tot=1,pre[N],n,m,k;ll fl[N],num;bool vis[N];inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){ if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x;}struct edge{ int n,to,l,f;}e[M];inline void add(int u,int v,int l,int f){ e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;e[tot].f=f; e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=0;e[tot].f=-f;}inline bool spfa(int s,int t){ memset(dis,0x3f,sizeof(dis)); dis[s]=0;q.push(s);fl[s]=inf; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=head[u];i;i=e[i].n){ int v=e[i].to; if(e[i].l&&dis[v]>dis[u]+e[i].f){ dis[v]=dis[u]+e[i].f;pre[v]=i;fl[v]=min(fl[u],1ll*e[i].l); if(!vis[v]){vis[v]=1;q.push(v);} } } } return dis[t]!=0x3f3f3f3f;}struct node{ int u,v,w;}a[M];inline void calc(int s,int t,ll mid){ int x=t; while(x!=s){ int i=pre[x]; e[i].l-=fl[t];e[i^1].l+=fl[t];x=e[i^1].to; } num+=max(0ll,1ll*(mid-dis[t]+1)*fl[t]);}inline bool check(ll mid){ memset(head,0,sizeof(head));tot=1;num=0; for(int i=1;i<=m;++i)add(a[i].u,a[i].v,a[i].w,1); while(spfa(0,n-1))calc(0,n-1,mid); return num>=k;}int main(){ while(scanf("%d%d%d",&n,&m,&k)!=EOF){ for(int i=1;i<=m;++i){a[i].u=rd();a[i].v=rd();a[i].w=rd();} ll l=0,r=1e12,ans=-1; while(l<=r){ ll mid=(l+r)>>1; if(check(mid)){ ans=mid;r=mid-1; }else l=mid+1; } if(~ans)printf("%d\n",ans);else printf("No solution\n"); } return 0;}