题目描述
汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领x名学生逃跑，整个学校可以抽象地看成一个有向图，图中有\(n\)个点，\(m\)条边。\(1\)号点为教室，\(n\)号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生，只有第一批学生全部逃生完毕后，第二批学生才能从\(1\)号点出发逃生，现在请你帮校长算算，每批最多能运出多少个学生，\(x\)名学生分几批才能运完。
输入输出格式
输入格式：
第一行\(3\)个整数\(n,m,x(x<2^{31},n<=200,m<=2000)\)；以下\(m\)行，每行三个整数\(a,b,c\)（描述一条边，分别代表从a点到b点有一条边，且可容纳c名学生)。
输出格式：
两个整数，分别表示每批最多能运出多少个学生，\(x\)名学生分几批才能运完。如果无法到达目的地（\(n\)号点）则输出“Orz Ni Jinan Saint Cow!”
输入输出样例
输入样例#1：
6 7 71 2 11 4 22 3 14 5 14 3 13 6 25 6 1
输出样例#1：
3 3
说明
【注释】
比如有图
1 2 100
2 3 1
\(100\)个学生先冲到\(2\)号点，然后\(1\)个\(1\)个慢慢沿\(2-3\)边走过去
\(18\)神牛规定这样是不可以的……
也就是说，每批学生必须同时从起点出发，并且同时到达终点
思路：这道题目相比其他最大流题目无非就是多了一个问要分几次运出，用\(k/ans\)判断一 下就可以了。
代码：
#include#include #include #include #define maxn 400007#define inf 0x3f3f3f3fusing namespace std;int m,k,S=1,T,head[maxn],num=1,d[maxn];inline int qread() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}struct node { int v,w,nxt;}e[maxn];inline void ct(int u, int v, int w) { e[++num].v=v; e[num].w=w; e[num].nxt=head[u]; head[u]=num;}inline bool bfs() { memset(d,-1,sizeof(d)); queue q; q.push(S),d[S]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(e[i].w&&d[v]==-1) { d[v]=d[u]+1; q.push(v); } } } return d[T]!=-1;}int dfs(int u, int f) { if(u==T) return f; int rest=f; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(d[v]==d[u]+1&&e[i].w&&rest) { int t=dfs(v,min(e[i].w,rest)); if(!t) d[v]=0; e[i].w-=t; e[i^1].w+=t; rest-=t; } } return f-rest;}inline int dinic() { int ans=0; while(bfs()) ans+=dfs(S,inf); return ans;}int main() { T=qread(),m=qread(),k=qread(); for(int i=1,u,v,w;i<=m;++i) { u=qread(),v=qread(),w=qread(); ct(u,v,w);ct(v,u,0); } int ans=dinic(); if(!ans) { printf("Orz Ni Jinan Saint Cow!\n"); return 0; } printf("%d ",ans); int tmp=k/ans; if(k%ans) ++tmp; printf("%d\n",tmp); return 0;}