当前位置: 代码迷 >> 综合 >> BZOJ 4669 抢夺
  详细解决方案

BZOJ 4669 抢夺

热度:60   发布时间:2024-01-19 01:55:03.0

Description

大战将至, 美国决定实行计划经济。美国西部总共有 N 个城市,编号
为 0 ? N ? 1,以及 M 条道路,道路是单向的。其中城市 0 是一个大城
市,里面住着 K 个人,而城市 N ? 1 是一个农业城市。现在所有城市 0 的
居民都需要到城市 N ? 1 去领取食物。由于担心体力不支,所以居民都会
采取开车的形式出行。但道路不是无限宽的,对于一条道路,会有 ci 的限
制,表示在同一天内,最多只能有 ci 辆车同时在这条道路上行驶。一条道
路的长度为 1,每辆车的行驶速度也可以假定为 1 每天。城市 N ? 1 会在
每个居民都到达后马上开始发放食物。现在 Reddington 想知道,假如在最
优安排下,居民最早能在多少天后领到食物。假如没有居民那就不需要发
放食物,默认为第 0 天。

Input

一个测试点包含多组数据。
对于每组数据:
第一行包括三个整数 N, M, K。
接下来 M 行,每行三个整数 u, v, c,描述一条从 u 出发到 v 的道路。
1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 0 ≤ K ≤10^9
0 ≤ u, v < N, 1 ≤ ci ≤ 109,数据组数不超过 10 组

Output

对于每组数据,
假如无解,输出”No solution”,不包括引号。
假如有解,输出最早的天数。

Sample Input

5 6 4
0 1 2
0 3 1
1 2 1
2 3 1
1 4 1
3 4 2

Sample Output

3
//第 1, 2 个人都选择第 0 天开始出发,分别走 0-1-4, 0-3-4 的道路,第
3,4 个人从第 1 天开始出发,沿着前两个人的路线走。总共只需要 3 天。可
以证明这是最优解。

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~

二分+费用流+思路~

首先可以看出来如果目前一次可以走k'个人,用时t,那么总共用时(k-k'+1)*t。所以只要做出每次可以走的人数和用时就可以得出答案。

二分答案ans,每次跑费用流,判断可不可以在ans的时间内跑完即可。

在更新答案的时候把a写成了dis,样例太水居然过掉了。写费用流的时候要注意区分a和dis啊。


#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;int n,m,k,x,y,val,fi[1001],w[10001],ne[10001],v[10001],cos[10001],kk[10001],las[1001],a[1001],dis[1001],cnt,inf,l,r,ans;
bool b[1001];queue<int> q;struct node{int x,y,val;
}ro[5001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int vv,int val)
{w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;cos[cnt]=1;kk[cnt]=u;w[++cnt]=u;ne[cnt]=fi[vv];fi[vv]=cnt;v[cnt]=0;cos[cnt]=-1;kk[cnt]=vv;
}bool findd()
{memset(dis,127/3,sizeof(dis));inf=dis[0];dis[0]=0;q.push(0);b[0]=1;a[0]=inf;while(!q.empty()){int k=q.front();q.pop();for(int i=fi[k];i;i=ne[i])if(v[i]>0 && dis[w[i]]>dis[k]+cos[i]){dis[w[i]]=dis[k]+cos[i];a[w[i]]=min(a[k],v[i]);las[w[i]]=i;if(!b[w[i]]){q.push(w[i]);b[w[i]]=1;}}b[k]=0;}return dis[n-1]!=inf;
}bool chec(int mid)
{int now=k;cnt=1;memset(fi,0,sizeof(fi));for(int i=1;i<=m;i++) add(ro[i].x,ro[i].y,ro[i].val);while(findd()){if(mid-dis[n-1]+1<0) return 0;now-=(mid-dis[n-1]+1)*a[n-1];if(now<=0) return 1;for(int i=n-1;i;i=kk[las[i]]){v[las[i]]-=a[n-1];v[las[i]^1]+=a[n-1];}}return 0;
}int main()
{while(scanf("%d",&n)!=EOF){m=read();k=read();ans=-1;for(int i=1;i<=m;i++) ro[i].x=read(),ro[i].y=read(),ro[i].val=read();if(!k){printf("0\n");continue;}l=1,r=n+k+1;while(l<=r){int mid=l+r>>1;if(chec(mid)) ans=mid,r=mid-1;else l=mid+1;}if(ans==-1) printf("No solution\n");else printf("%d\n",ans);}return 0;
}