Description
在一段时间之后，网络公司终于有了一定的知名度，也开始收到一些订单，其中最大的一宗来自B市。Blue Mary决定亲自去签下这份订单。为了节省旅行经费，他的某个金融顾问建议只购买U航空公司的机票。U航空公司的所有航班每天都只有一班，并且都是上午出发当天下午到达的，所以他们每人每天只能坐一班飞机。经过调查，他们得到了U航空公司经营的所有航班的详细信息，这包括每一航班的出发地，目的地以及最多能买到的某一天出发的票数。(注意: 对于一个确定的航班，无论是哪一天，他们最多能买到的那一天出发的票数都是相同的。) Blue Mary注意到他们一定可以只乘坐U航空公司的航班就从A市到达B市，但是，由于每一航班能买到的票的数量的限制，他们所有人可能不能在同一天到达B市。所以现在Blue Mary需要你的帮助，设计一个旅行方案使得最后到达B市的人的到达时间最早。
Input
第一行包含3个正整数N，M和T。题目中会出现的所有城市分别编号为1,2,…,N，其中城市A编号一定为1，城市B编号一定为N. U公司一共有M条（单向）航班。而连Blue Mary在内，公司一共有T个人要从A市前往B市。 以下M行，每行包含3个正整数X,Y,Z, 表示U公司的每一条航班的出发地，目的地以及Blue Mary最多能够买到的这一航班某一天出发的票数。(即：无论是哪一天，Blue Mary最多只能买到Z张U航空公司的从城市X出发到城市Y的机票。) 输入保证从一个城市到另一个城市的单向航班最多只有一个。
Output
仅有一行，包含一个正整数，表示最后到达B市的人的最早到达时间。假设他们第一次乘飞机的那一天是第一天。
Sample Input
3 3 5
1 2 1
2 3 5
3 1 4
1 2 1
2 3 5
3 1 4
Sample Output
6
HINT
约定：
2 <= N <= 50
1 <= M <= 2450
1 <= T <= 50
1 <= X，Y <= N
X != Y
1 <= Z <= 50
Source
做过紧急疏散这个题就是一眼题了，考虑二分答案然后按时间拆点用判满流来check即可；
注意二分大上界为n+tot,因为tot个人排队走即可，一开始设为n*tot狂T不止；
//MADE BY QT666#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>using namespace std;typedef long long ll;const int N=200050;const int Inf=19260817;int head[N],to[N],nxt[N],s[N],S,T,cnt=1,level[N],vis[N],q[N*10],F,n,m,tot;void Addedge(int x,int y,int z) { ???to[++cnt]=y,s[cnt]=z,nxt[cnt]=head[x],head[x]=cnt;}void lnk(int x,int y,int z){ ???Addedge(x,y,z);Addedge(y,x,0);}bool bfs(){ ???for(int i=S;i<=T;i++) level[i]=0,vis[i]=0; ???int t=0,sum=1; ???q[0]=S,level[S]=1,vis[S]=1; ???while(t<sum){int now=q[t++];if(now==T) return 1;for(int i=head[now];i;i=nxt[i]){ ???int y=to[i]; ???if(level[y]==0&&s[i]){level[y]=level[now]+1;q[sum++]=y; ???}} ???} ???return 0;}int dfs(int now,int maxf){ ???if(now==T) return maxf; ???int ret=0; ???for(int i=head[now];i;i=nxt[i]) {int y=to[i],f=s[i];if(level[y]==level[now]+1&&f) { ???int minn=min(maxf-ret,f); ???f=dfs(y,minn); ???s[i]-=f;s[i^1]+=f;ret+=f; ???if(ret==maxf) break;} ???} ???if(!ret) level[now]=0; ???return ret;}void Dinic(){ ???while(bfs()) F+=dfs(S,Inf);}struct data{ ???int to,lim;};vector<data> p[100];struct date{ ???int id[2505];}g[100];bool check(int mid){ ???memset(head,0,sizeof(head));cnt=1;int tt=0; ???for(int i=1;i<=n;i++){for(int j=0;j<=mid;j++) g[i].id[j]=++tt; ???} ???S=0,T=tt+1; ???for(int i=1;i<=n;i++){for(int j=0;j<p[i].size();j++){ ???int x=p[i][j].to,lim=p[i][j].lim; ???for(int k=0;k<mid;k++){lnk(g[i].id[k],g[x].id[k+1],lim); ???}}for(int k=0;k<mid;k++) lnk(g[i].id[k],g[i].id[k+1],Inf); ???} ???lnk(S,g[1].id[0],tot); ???for(int i=0;i<=mid;i++) lnk(g[n].id[i],T,Inf); ???F=0;Dinic(); ???return F==tot; }int main(){ ???scanf("%d%d%d",&n,&m,&tot); ???for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);p[x].push_back((data){y,z}); ???} ???int l=0,r=n+tot,ans=0; ???while(l<=r){int mid=(l+r)>>1;if(check(mid)) r=mid-1,ans=mid;else l=mid+1; ???} ???printf("%d\n",ans); ???return 0;}bzoj 1570: [JSOI2008]Blue Mary的旅行
原文地址：http://www.cnblogs.com/qt666/p/7625201.html